For a 'traditional' map, you can't go wrong with Ascension's antique-style tutorial: http://www.cartographersguild.com/tu...photoshop.html

You might also just do a more detailed black & white map; with enough detail they can look pretty awesome.