I heartily recommend that everyone purchase a copy of Fractal Terrains Pro (it also makes an excellent gift!)
Now that the self-serving endorsement is out of the way, I recommend looking at http://www.shadedrelief.com/ when you've got a little time to kill. Tom Patterson offers many suggestions on doing exactly the sorts of thing you describe.