If people choose to follow the steps below, my one word of advice is to EXPERIMENT as some of the selections I make for this tutorial may not be right for your map. This is the technique I used to produce the maps found in the Lands section of the Encyclopaedia.
I'm assuming that people know The Gimp and are aware of how to handle layers. The other tools needed are the pencil (n) - don't use the paintbrush, flood fills (shift+b), colour selector (shift+o), colour picker (o) and finding their way to the "change foreground colour" dialogue box.
Scribble a map out in the gimp - doesn't need to be wonderful, but an indication of where you want coastlines, mountain chains and rivers will be useful. Also at this stage, decide how detailed you want your map to be. More detail means you'll need to produce a finer greyscale map, which means lots more time.

Make a new layer. Using a white foreground colour (hex: FFFFFF) mark out the top of the highest mountain. Then change the foreground colour to a darker shade of grey (say hex: FAFAFA) and mark out the next lowest elevation. Make sure the elevations are solid colours. Repeat ...

... and repeat ...

... and repeat, until all your land is filled with different shades of grey.

Things to remember include the fact that mountains are craggy, and a bit waxy; they have spurs and lobes and cliffs and stuff. But at the same time they have order, and often join up into chains and lines - ranges of mountains.
When I was doing my big map, I found it useful to use Gimp's quickmask to speed up the process:

Though I'm no expert at using the quickmask and occasionally id manage to lose a couple of hours work through my own stupid ignorance.

Anyways, after you've got your greyscale map (equivalent to a DEM map) you can start to have fun.
Using the colour selector, select just the mountainous (lighter) bits of the map and copy them onto a new layer ...

... and fill in the rest of the layer with a grey that's slightly darker than the lowest bit of the mountains

Do a blur on this layer - experiment to see what sort of blur works best for you (I used filters > blur > gaussian blur):

And then do an emboss - again, experiment (I've used filters > distorts > emboss); the azimuth thingy will decide where the sun is over the map while the depth thingy determines how bright and dark the mountains will be:

Now go back to your greyscale map and make a copy of it as a new layer. Select each grey elevation in turn and flood it with a colour of your choice - choosing the best colour scale is entirely up to you as this is where a lot of the artistry of mapmaking happens. Some people prefer purple mountains, whereas I went for a sort of greeny-yellowy-browny effect.

Then by playing around with the transparency levels of the colour map you can get the embossed mountains to poke through to give a 3-D effect

I divided my colourmap into 2 layers - lowland and highland - so that I could apply different transparencies to each.

Well, that's the end of this dog-rough tutorial. There's lots of improvements that can be made to the final result - for instance doing a slight blur on the colourmap layer would certainly make it look more realistic. Coastlines can be done by highlighting all the land and doing a "stroke selection" thingy to give that nice thin line around the coasts. Rivers are easy using the greyscale map - just remember they'll start in the mountains and always take the quickest path down to the sea, always moving from ligher grey areas to darker grey ones. And adding rivers, cities, roads, labels, etc on their own layers makes it much easier to play with their colours and transparencies and stuff to give you the final result you're looking for:
