I agree, I think that there should be a navigation system. In addition to a proper compass, with 32 points, not degrees since that isn't period correct, I would also like to see a celestial navigation mechanic added.
The way I'm think it should be simple enough. You would have to add latitude and longitude to the map. At noon, you would get a latitude reading, nothing to precise, a whole degree should be fine since that represents 60 miles. If players purchase a chronometer, then they get a circle saying you are with in x miles of this point. but you only get this information once a day at noon.
After you have this information, you can use dead reckoning to figure your way to your destination.