There are a couple of things you need to make a map:
1) A program such as Gimp or Photoshop (Gimp's free and easier to use in my opinion)
2) And some creativity. :)
Once you've got those you can start with the first step, and that's making what is called a height map which determines how lumpy or flat the land in your map will be.
This section (http://www.feral-heart.com/index.php?option=com_content&view=article&id=6&Itemid=11) in the manual shows you how to do it.
On completing the height map, you can move onto the terrain mask, which is like the height map, but it determines the textures of the terrain rather than the height. You can make it with 3 colours or 6 colours, but 3 colours will be a lot easier to start with.
Crin has made a nice little tutorial for this: http://www.feral-heart.com/index.php?option=com_jfusion&Itemid=2&jfile=index.php&topic=17452.0 (http://www.feral-heart.com/index.php?option=com_jfusion&Itemid=2&jfile=index.php&topic=17452.0).
When all that's done, you can start using the map maker, which is in the tools menu when you start up FH. This (http://www.feral-heart.com/index.php?option=com_content&view=article&id=5&Itemid=9) is pretty helpful in showing you how. The map maker lets you put objects, such as trees and rocks, in your map so go nuts and explore around with the controls a bit. But remember to save your progress! There's nothing more frustrating than loosing an hour's worth of work on a map.
Good luck with your map making! :)