I think this is a really neat idea! Without offering any specific advice I would advise you check out the different tutorials on this site as they will likely be able to answer a number of questions pretty well. In all likelyhood if you want to use vectors you may need to just redraw your map in a program that deals with vectors such as illustrator or inkscape (which is free to download) A lot of people just use photoshop for everything and make sure the resolution is high enough to allow for sufficient smoothness. Rasterized (pixelated art as opposed to vector art) has its limitations. For example, if you make a rasterized map intended for printing you will want to make sure to set the image at 300 dpi before starting work or it won't print well. One way to get that paper feel in photoshop is to get a large parchment image and lay it under or over your drawn lines with low opacity or some sort of blending option. There are several ways to do it and you'd need to do some experimentation to get what you want.