Welcome to the Guild Authur!
If you are new to Photoshop in general, be sure to check out both
The sticky by RPMiller here: Photoshop Basics and
Pyrandon's VIDEO tutorial(s) for the PS neophyte100% Photoshop mapping newbie? Here's a video tut for you
City map tuts by Pyrondon: Eneini: a medieval city tutorial (in Photoshop)
Koppollex: A medieval town map tutorial in Photoshop
Ravells: how to draw nice maps - intro level [photoshop]
Pyrandons map for making an artsy type regional map:My Thracioth map walk-thru (Photoshop)
Also, don't be afraid to take a look at some other tutorials after you let the above sink in. Though some of the techniques might be a bit different, many of the things you can do in GIMP can be done in Photoshop and visa versa, though you might have to get some creative workarounds.
Also, post up your works in progress in new threads and let us know the software used each time (or put it into your sig if you use the same thing). We will be more than happy to help point you in the right direction along each step.
Design philosophy stuff:
Though there are many different thoughts, here are my thoughts on how things should be done and the order:
Regional or World map:
legend (though a simple, throwaway scale is nice at the first stage!)
For Cities and towns, you have to do some more thinking ahead of time. For example, is the town/city planned or did it just grow? This is super important if you want to put up any type of stonework or walls or such. If planned, you have a bit more free reign, but if it grew slowly, then you have to be careful with your placement of walls. Very few fantasy cities could afford a 3 mile long wall circling a city unless resources were abundant or some type of magic was involved. What generally happened if a city was constantly being attacked is that multiple walls sprouted up from around (ie, radiating outward from) a central defensible point over time. So a small wall is built, then as people move to the city and live on the outskirts and get attached, a new wall might be built a bit larger around the original and this process may continue several times over a hundreds of years. Likewise, unless the land outside the city is super bad, there will always be some outliers for farms, perhaps brave nobles, etc who don't want to(or can't afford to) live in the city proper. For farms, you must have someone to tend the crops and in most cases, someone is not going to walk for an hour from the city out to the farms everyday.
Another thing to think about is where does the waste go? Dead, food scrapes, human waste, etc. A fast moving river is usually a good dumping place (well, for the people who need to get rid of it, not necessarily in general or for the people downstream!) Things like paved streets, while nice are not going to happen often again unless magic or the kingdom is wealthy, at least not on every path (there may be some.) If you try shadows on buildings, be careful, a drop shadow tends to make things look like they are floating while an outer glow gets the illusion of height without the floating thing.
Well, I am sure there is some stuff I missed, but this should get you started. And again, if you are not sure of something, just post up a copy of your map and we will try to help you out.