I'm going to go for what GP said in your intro thread. Your best bet, IMHO, is to do it by hand and scan it.
Try some test maps on paper using pencil in the style you think you want...I'm picturing the old black and white map from the front of LotR. Refine the design then try lightly sketching in pencil and inking over that.
You can use an inking pen (I use Staedtler pigment liners but there are other brands) or try a nib pen and ink (I have had good results). For a final map I recommend a smooth paper that's not too absorbent or grainy. I used smooth bristol board, Strathmore, more a recent map with good results.
Once done, you can scan it in. If you do it in a large format you can take it to Kinkos or similar and have them scan it for you...not too expensive. I think having them scan it in color is the best. I tried greyscale with them and it ended up being half-time dots for some reason.
You should find a thread on hand-drawn maps in the tutorial sections. It covers materials and such very nicely.
Hope any of that helps!
N.B. It likely *will* take quite a lot of time to design, refine, and finally create your map. I spent many long hours creating this map for my gaming world. There aren't really many short-cuts...although much of my time was spent coloring and texturing and you won't have to do that for your map I think.[/edit]