There are ways to make maps, and there are ways to make maps.
This is an alternative tutorial written by kyle and syllabear that's more intended for beginners who haven't dealt with XML before. It basically contains duplicate information to the page above, so for technical matters Making Maps by Hand should be consulted.
This is the only supported way to make maps right now. It is a tutorial that is created by the Map Master himself and hopefully maintained by him (with everyone's help). It is your first and best resource to what exactly goes into a map, how to put it there, and how it works in the game. Even if you choose to use a graphical map maker, you still need to read this, so consider it required reading.
Tools and Generators
Nemostultae made a neat little web application that renders a map to a picture right in your browser. When used in conjunction with a text editor, it is a powerful tool to help make maps. In fact, the output of this page is currently considered required information if you want any server administrator to use your map on his server.
So you've made your killer map, now how do you play it?