Two Part Post... part one.
I used Photoshop CS, so obviously the GiMP users will need to adjust accordingly.
First a new document, I wanted a roughly earth sized map and at a resolution that I could adjust easily into large regional maps. I went with 10 miles to the pixel and opened a document 2400 by 1200 pixels.
To create the rough terrain layer create a new layer. With the foreground and background colors as black and white, Click Filter > Render > Clouds to create a simple random field. Now Click Filter > Render > Difference Clouds to exaggerate the contrast. I used Difference Clouds three additional times (Ctrl+F) to get the nice ribbon like areas that formed my mountain ridges.
Next outline the general landmasses, similar to the "Not So Random Coastlines" tutorial. I could draw them with big fuzzy white brush but I used a second layer and selected only about 1/4 of it's size. Use Filter > Render >Clouds again to generate some rough light and dark areas and a quick Gaussian Blur to smooth it out. Then I used the Transform (Ctrl+T) to resize the selected area until it covered my entire image. I then used a curves adjustment to get lots of pure white areas and pure black ones, with the fuzzy gray between them.
Whether I drew my rough landmasses or simply generated clouds, I had to meld the two layers. The new layer with the general landmasses should have it's blending mode set to "Screen" and it's opacity to about 60%.
In order to avoid islands and continents that hit the edge of my map, I added a third layer. Set it's Blending Mode to Multiply and Hit CTRL+A to select the entire image. Click Select > Modify > Contract and bring the selection in about 30 pixels from the border. Click Select > Feather with 25 px to soften the edges. Click Select > Invert to that you only have the border around the edges selected. And finally click Edit > Fill and select Black. This will create a faded black edge around the image to make sure none of your landmasses fall off the edge of the world. You can edit this with a further blur or even paint out areas that you know you want to be oceans.
When I retraced my steps in writing this tutorial, I had this. (At 25% size for bandwidth's sake.)
And my Layers palette looked like this.
Now the fun part!
With the pure white as the foreground color click Select > Color Range and set the fuzziness to about 180 or so. You should get a selection that closely matches the lighter areas of the image. Click Select > Save Selection and name it something obvious, like "Height map".
Create a new layer and fill it with a blue for your oceans. Create another new layer and load the Height map selection. I like to Expand then contract the selection to eliminate the fuzzy areas in the middle. Don't do a lot of manual painting on the layer mask as it will lead to areas not correlating to the height map later. Click Layer > Add Layer Mask > Reveal Selection. This will give you a layer mask to isolate the landmasses.
Now to make the height map itself. Create a new layer above all of the existing layers. Fill it with 50% gray. Click Filter > Render > Lighting Effects. I like to use a directional light so that all my shaded relief mountains are shaded in the same direction.
These are the settings I used.
This is the map in it's gray form.