The colors in this map reminds of Torq's October Challenge Map, style too. Torq used GIMP, so I imagine Photoshop would be just fine to create maps like this. Some of the mountains look like fractal generated mountains, while some of it just look like brush strokes with shadowing applied. I see embossed/pillowed river banks also similar to Torq's map.

I like the rivers and lakes in this map - nice job on this one.

You might consider downloading GIMP as this is free and their are many great tutorials here for GIMP. (Since GIMP is very much like PS, you should catch on fairly fast - even going back to PS and trying similar techniques there.)

Look at the various fractal noise generators to create your mountains.