In addition to L.Dutch's answer:
As well as clock, sextant and tables, I'd suggest a map.
Many aerial views have been accrued of the Red Planet, at different times of day with different shadow-lengths. The topography can be calculated from this leading to 3d maps on a tablet-like computer.
In any place on the surface, the view from the ground can be compared with the map (via camera) - the computer then compares the view with the model, giving a probability of being at a certain latitude/longitude. At the very least they should have an interactive map of the terrain. The benefits are obvious.
Combined into a single instrument as per @John's comment, this would be powerful and compact.
The downside:
On flat plains (of which mars has a few), the horizon may not contain any identifying features, or not sufficient of them to identify location. It would be hit and miss at night as to how much it might help (clouds). It would require charging in order to function, solar is fine, but overuse might leave the equipment unusable 'till charged again. A single instrument doing everything is a single point of failure for the navigating capacity - unless they can make a makeshift sextant from "stuff" around.