I would scan the existing map and trace over the image in Photoshop.
Or, you could preserve your existing line work. Place a new layer below the scanned image, and set the scan's blend mode to Multiply. Multiply will eliminate the white of the paper and mix the darker colors into the underlying layer. You'd still have to find a way to remove the graph paper lines, probably. If they're light enough, a Curves or Levels adjustment might be enough to remove them, in addition to strengthening the lines you want to keep.
When I use a scanned drawing, I like to scan it at 600 dpi, blur by 2 pixels, then scale it down 50%. I find this makes the lines look nicer than if I scan at 300 dpi to start with.