Well, we do have this tutorial here on the site, but it's somewhat outdated, it should give you the main idea however.
http://feral-heart.com/index.php?option=com_content&view=article&id=6&Itemid=11I will try to explain as easy as possible, and someone else might fill you in some more later.
But yes, you need gimp or photoshop for the mapmaking, and actually some basic knowledge on how to use it.
Now lets say you already know how to.
Go into the game and create a new map in the map maker, give it a name and just save it. Don't do anything more or less.
Now go into C:\FeralHeart\media\terrains
Find the watermill folder and copy the watermillterrain.png picture, and paste it into C:\FeralHeart\media\terrains\(the mapname of the map you created here)
That way you will have a already completed heightmap inside your map folder.
This is just the heightmap of watermill though. so once you tried it inside the map maker, loading it for your make and seeing the heigth differences, you'd need to open it with either gimp or photshop, and then edit it around.
Save the picture as a grayscale image without layers and something like 512 x 512 in size.
once you enter the map maker the next time it should have a different look.
That's the basic you need to get started.
Learn by doing I'd say.