I'm assuming that you need to put directions on a brochure/leaflet... Most people (in print) draw their own in Illustrator. It doesn't have to be dead accurate usually a general one showing the A/main roads and then perhaps a detailed bit of how to find the end destination - small roads etc.
Just make sure that you get the right number of roundabouts... I once sent all the people coming to my house warming to the wrong side of the river we lived near - missed out a vital roundabout!
A word of warning to anyone planning to use or copy a map from Google, Bing, etc. Many of these maps features "trap streets" (I think they're also called "oxygen streets"). These are basically fake or altered streets unique to a specific provider that are intended to identity anyone copying their maps without permission.
I'm not sure what the legality is of tracing over a map, but either way I'd recommend cross-referencing.
I would think if you are tracing over a map and recreating it you are safe from the 'map police'. I've redrawn my local area loads of times - keep them all in a map folder so that they are easily adaptable for the next client.