I've lurked on the tutorial forums for a while, learning the tricks of the trade, and I figured I should try and give something back.
I really like the old-school style maps using not-to-scale graphical representations of objects of interest. I've adapted a number of the ideas I learned on these forums to develop a quick and easy technique for making this style map in my open source graphics software of choice, the GIMP. I wrote up a tutorial and attached it as a PDF. Running through the tutorial should take 1-2 hours (depending on your familiarity with the program) and you'll wind up with a map like the Sample map attached. Once you've got your brushes made and the technique down, you can churn out maps very quickly - the Sample map took me 15 minutes to make from a blank canvas. If you spend more time you can make much nicer maps using the same techniques.
The tutorial is written so someone completely new to GIMP can start using it to make maps. A more experienced user can easily get by with just skimming the highlights. The most important portion is the creation of the animated brushes and correctly tuning their spacing.
A caveat - these maps are not (nor are they meant to be) strictly geographically accurate. You'll notice the sample map doesn't have so much as a compass rose, let alone a scale bar. They're meant to give a general representation of an area. This is sufficient for some purposes and not for others. I use them as RPG handouts to give players an idea of their immediate area. It is of course not difficult to adapt these techniques towards the production of more accurate maps.