During the medieval times, trade caravans using camels criss crossed the Sahara and Meghreb. For example, salt caravans from the Empire of Mali to the near east. I've wondered for a long time how they could navigate these long distances in unremarkable, or constantly shifting terrain, without a compass. I can imagine at night they could use the stars to get some bearing, but in the day time with the sun directly overhead, how did they know which way to go?
The exact technique these caravans used to navigate the desert appears to an issue of some contention in the scholarly community. Solid historical evidence seems to be lacking, since these cultures orally passed down this navigation knowledge for the most part. Anthropologists and other scholars have made analyses of modern Saharan navigators, but the questions remains of whether these modern peoples use the same techniques as they did historically.
However, even with all that, there seem to be two main theories for how these peoples navigated.
- Navigate using the stars: There seems to be some evidence that modern Tuareg people of the Sahara navigate using star formations and astronomical knowledge. While it appears that these people never developed highly sophisticated astronomy, they know/knew enough for basic navigation. See this link for more information on this theory.
- Navigate using landmarks: However, there is also strong evidence that the same modern Tuareg people primarily use landmarks to navigate, occasionally in conjunction with star-based navigation, but often alone. While this technique would not allow people to navigate over many of the large, shifting-sands regions of the Sahara, most of the Sahara actually has visible rock formations that could be used for this purpose. See this link for more information on this theory.
It is also possible that the medieval navigators used some combination of the two techniques, using landmarks when they were available, and using their rudimentary astronomical knowledge only when landmarks were unavailable.
- There are much sand in Sahara, that's true. But the sand deserts are mixed with stone or clay ones. And these last are everywhere in Sahara. (BTW, the sand deserts are the least dangerous - there are always some water somewhere under the sand.) So, it is enough to choose ways so that you'll visit periodically these stable parts of Sahara. Or at least see them sometimes - viz. p.2.
- The people in Sahara used the stone "lighthouses" - heaps of stones on some ordinary hills, and the extraordinary rocks/hills/mountains themselves as orienteering points. These travellers even renewed such heaps on sand dunes - the dunes are not changing during a day or even a month.
- Of course, nobody travels Sahara in midday, and in the evening/morning the Sun can be used for orienteering. And, of course, the Polar star at night. (In the old times the Polar star was not polar, but always there was some other near-polar star.) The precision of that course is enough to reach from one orientation point to another.
And where it was not enough, there was no caravan ways.