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

http://rpgmapshare.com/index.php?q=gallery&g2_itemId=19
Dungeon Channel

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