I am surprised that no one has yet mentioned the Gyrocompass: https://en.wikipedia.org/wiki/Gyrocompass

The post mentions manually-set directional gyroscopes, but gyrocompasses are a step ahead of that; on any sufficiently-quickly-rotating planet, a gyrocompass will point you towards the geographic poles by noting the axis of precession of a gyroscope with arbitrary orientation. That's even better than a magnetic compass on Earth, since the magnetic poles do not line up exactly with the geographic poles, and the magnetic is non-uniform anyway (which is why navigational charts include notations of the magnetic deviation in different areas).

Celestial navigation plus accurate clocks. I'd think this would be especially good on a planet without clouds (as long as your planet rotates fast enough, so I guess Mercury is out). Anyone know if Mars has any polar stars?

https://en.wikipedia.org/wiki/Celestial_navigation

Venus too - and this is also why neither have water - no strong magnetic field to hold the heliopause at bay, so the solar wind blows water out of the atmosphere.

Does having "no strong magnetic field" mean no Ionosphere and thus no Shortwave Radio?

KRET develops stellar navigation system for Russian strategic bombers

http://www.janes.com/article/52661/kret-develops-stellar-nav...

Already done? More than 40 years ago, but probably still workable:

https://en.wikipedia.org/wiki/Lunar_Roving_Vehicle#Control_a...

stellar inertial navigation - It means that as well as an inertial system you track the stars... which are actually visible even during daylight through an automated telecope system... although not through cloud I guess.

Pricey but so is getting to Mars

GPS