A quick run-down of how I made the map up to this point (note that I use Photoshop 7, not Photoshop CS4):
For the landmass:
New layer, apply the render -> clouds filter with standard black and white colours selected. Make a Threshold adjustment layer and fiddle with the threshold level until you see something you like. Copy and move around segments of land that you want elsewhere, and use the burn and dodge tools to add and remove land. Select the final land shape, make a new layer and fill the selection with your basic soil colour (in this case, fairly bright green).
For the mountains:
Select the landmass, apply
render -> clouds and then apply
render -> difference clouds twice. Select and delete the darker areas of this layer, and set the blending mode to overlay or multiply, depending on how dark or bright you want things. You'll likely have to play with this layer's overall brightness and contrast to get something that works. You can then select this layer, make a new one and repeat the process to get some extra peaks on top of it. Select the lightest shades of the peak layer and fill a new layer on top with white to make snowy peaks. You can decrease the opacity and repeat the process on just the very bightest shades if you feel that once isn't enough.
For this map, the base mountain layer is light grey and set to multiply, and the peak mountain layer is slightly darker grey and set to overlay.
For the coasline:
I have a white outer glow on the basic green landmass layer. I duplicated the landmass layer, and gave the duplicate a thinner, brown outer glow to make it flow into the white outer glow below it. I also added a similar thin brown inner glow to make the transition smooth on that side as well.
As for the rivers and the ocean, the previous posts in this thread give plenty of information on those aspects. And the textures are generally just that; textures overlaid onto the layer, and then sufficiently altered to look the way you want them to, which mostly means playing with the blend mode and their brightness and contrast.
I think that many of the methods used come from things I read in Ascension's tutorials, such as the way I made the mountains, and the gradient overlay I used on the landmass to have greens and browns fade into eachother.
That's about all I can think of. Hope it's useful.
Now to get back to actually mapping, instead of writing about it.