Not wayfinding on the land, but I'm told The Barefoot Navigator by Jack Lagan is good.
"The first part of this absorbing book recounts a colourful history of seafarers and their navigation techniques. How did the Polynesians manage to populate an area of ocean larger than North America simply by analysing clouds,currents and wind direction? How did the Vikings routinely travel on the notorious stretches of water between Iceland, Greenland and Scandinavia?"
This reminded me of these amazing things: Greenland Inuit people used to make tactile, carved maps of the coastline and islands they navigated - you "looked" at them by touch. Ammassalik maps.
I always remember this map from Ian Armit, 1996 (first seen as a student):
An island centred geography - by flipping the map, we can see more easily how in a world without roads the seaways are the key to connectivity. In continental Europe navigable rivers (a wider category in smaller boats!) and large lakes would have been similarly important.