Here's the process I used to make the map, plus a big, printable version at the end.
Drawing the Map
I drew the map separately from the "Kiris Dahn" name and the compass rose. Starting with a pencil sketch of the most important places (skipping details like the trees and the small buildings), I then went back in with a Memory brush pen. (It's kind of like a spongy material shaped like a brush for doing flowing lines with permanent ink.) Here's a photo I took during inking:
After inking, I erased the pencil lines, then went back in with a brown pen brush to add details in a lighter value. On a separate piece of paper, I made the Kiris Dahn name and compass rose. (I just used cheap printing paper since I knew I'd be heavily photoshopping this.) I then scanned the maps. The WotC scanner had some solidified gunk on it that left some big dirt smudges in the scanned images. They looked enough like they could be wear and tear on the PCs' copy of the map that I didn't try too hard to remove them.
To put it on a semi-parchment background, I tore the edges off a manila envelope, crumpled it up, flattened it back out, and scanned it. After manipulating it in Photoshop to make it lighter and less saturated, I put together a document with the illustrations layered on top. Here's the raw background image alongside a detail from the final document:
I ended up with a map that does what I wanted it to: emphasize the important places of Kiris Dahn and look like a reasonable prop for the PCs to possess. Most RPG maps, in my opinion, look too modern to hand out and keep verisimilitude. Not many D&D NPCs would have Photoshop or satellite imagery to make their maps, nor would every city's cartographer be a master draftsman. Finally, here's the final map, at its original size (click for the full-size image):