Like Midgardsormr said, JPG is usually the most common format.

I think some VTTs use grid squares of 50x50, but 100x100 is more common I believe (1 square = 100x100 pixels = 5 feet), so probably best to go with that IMO (that's how I make mine, and I've had no complaints), and if they need a smaller size, they can just resize it down themselves.

Once you've figured out the scale of your map and resized it, you're done for the gridless version. But I definitely agree with Midgardsormr, that including a gridded version is also a good idea. To do that, you'll need a grid with a transparent background. (If you need help with that, I can make one for you, at whatever dimensions you want). Then you just add the grid as a new layer on top of your map, merge the two and again, save in .JPG format. You can also play with brightness/contrast, colours, drop shadows, layer modes and transparency, etc. to get different effects for the grid, and make it more esthetically pleasing and such. For example, just dropping a solid black grid on top of your map probably wouldn't look very good. And I've seen other people use solid colours like bright yellow, which looks...very ugly, and distracts from the actual art of the map.

Can you link us to one of the maps you'd like to convert for VTT? Having a visual might help with giving you more specific information on what you can (or need) to do.