If the planet had a decent magnetic field, it might actually be quite easy to navigate. A sextant would get you "solar latitude" as it were (the angle of the sun relative to the horizon defines a circle), and coupled with magnetic orientation I think that would narrow it down to one of four points on the day side of the planet (where the field lines have a given angle with the radius of the previously defined circle). Given even crude object permanence I think that should fix your position pretty well.