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...)

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