Natural navigation has long been used by those travelling in extreme environments, like the Arctic and the desert.
The sun, moon and stars can of course still be used in these environments, but one technique that is specific to these parts is an intimate understanding of the way the wind sculpts the land's surface. The North American Inuit are able to read the shape of the ice's surface and from this work out which wind caused the each 'sastrugi' or ice ridge to form. This gives them a strong sense of direction in even the worst visibility.
In the Sahara, traditionally nomadic cultures, like the Bedouin or Tuareg, read sand in a similar way.
I have studied these methods in the Libyan Sahara with the Tuareg, in Borneo with the Dayak and led my own research expeditions into the Arctic. I have taught these techniques to groups from the UK to Oman.