On this planet space is non-euclidian in an non-uniform way. This means that two random points (A and B) on this planet could have the following properties (exact numbers are arbitrary):
One could rotate 430° in order to complete a full rotatio at point A and 250° at point B.
To get to point B from point A one could face 90° at point A and walk 2 meters, one could face 200° at point A and walk 5 kilometres or on could face 423° at point A and walk 400 metres.
One could create a tringle using points A, B and C and have an internal sum of angles of 54°. While one could create a different triangle with an internal sum of 190° with points A, B and D.
In other words. Each point on the planet's surface can have more or less space than usual surrounding it and be connected to any other point on the surface in a way that is impossible in standard 3d space.
There are large parts of the planet that have far less extreme geometry and that can be traversed without mental gymnastics. How would the inhabitants of these parts go about traversing the more extreme parts? How would they find the shortest path between two places? Would this even be a significant impediment to a society with our technology level?
Assume the following:
The planet has a regular rotation.
A magnetic north exists in a single place on the planet that a compass would point to.
The planet orbits its star like a regular planet.
Close orbits to the planet experience similar effects.
First, it's worth noting that navigating on the surface of the earth can be considered non-Euclidean, as it is a spherical geometry. But on earth this is a uniform phenomenon (not changing from place to place). So with this in mind, below are the steps that would be likely.
Step 1: "Map" the surface. Not just the landmarks, but how the local geometry and topology changes depending on where you are. There are many types of non-Euclidean geometries, and figuring out which one (or ones) apply will be vital.
Step 2: Depending on how complicated the geometry and topology are will dictate the level of complexity needed to navigate. Anyone would have to know their current position as well as the local relative direction that they need to go in order to navigate.
Step 3: It may just be so complicated (the level of complexity depends on how drastically and quickly the topology changes) that navigation requires full computer modeling and your society may just need a modified version of a GPS in order to effectively navigate.