Regardless of your photo-editing software of choice, here are some links that you can use for map creation.

Map Making Online

Here are some online map making tools that you can use to make maps for Roll20.
Dave's Mapper
AnaMap
Dungeon Painter Online
Tiamat The Tile Mapper
Donjon - both Dungeon map and general stuff generator (encounters, towns, calendars, NPC, traps, treasures...)
Mipui
Hextml - hex map maker with submaps
GM Friend Hex Map Making Tool - hex map maker with subhexes and random generation

Paint Brushes

http://www.obsidiandawn.com/category/brushes
http://www.redmondpie.com/download-adobe-photoshop-cs2-for-free-legally-while-you-still-can/

Pre-done maps

• RPG Map Share
• Dungeon Channel
• Historic City Maps
• Papertowns on Reddit

Textures

http://www.texturemate.com/category/image-galleries/asphalt

Tokens & such

http://www.rpgmapshare.com/index.php?q=gallery&g2_itemId=564&g2_page=24
http://rpgvirtualtabletop.wikidot.com/tokens

Tutorials

• Creating your own battlemaps – a simple tutorial
  
• How to draw a map - excellent site for Painterly maps
• Dyson Logos - amazing sketched maps and tutorials
• Plexsoup on Youtube - Blender, Gimp, Inkscape, Roll20
• Mapmaking on Reddit
• Cartographer's Guild

See Also

• Isometric Maps in Roll20
• Geomorphic Map Tiles
• Game Resources