Other answers have talked about concepts of north, south, east, west, outward, inward, etc. But there's the additional problem of finding your current longitude and latitude, which is something a compass cannot provide.
Your first method of figuring these out would be simple landmark navigation. Go north from Jumpoff Point to the Isle of Reckoning. From there, head north-northwest until you sea the Misty Lagoon over the horizon. Etc.
But we can use the sun and the stars to get much better positional data. At first, your people might have no concept of stars or star-mapping, because the ever present Sun in their sky might hide all the stars, depending on the atmospheric conditions present. However, if it's like Earth, we can still see a few stars on the horizon opposite the Sun at dusk and dawn. Likewise, your people would see the stars, and recognize that certain stars are visible at certain times of day.
Summary.
A simple sextant will give your mariners their current latitude by measuring the vertical angle of the Sun at noon (or some other object at its apex in the sky). Using accurate clocks can allow calculations at times other than noon.
Longitude is much more difficult, requiring precise time-keeping to measure. While the math itself is easy, we didn't develop properly precise clocks until the late 1700s.1
As such, landmark navigation will remain common for quite some time, particularly for longitude.
Time of Day defined.
For the sake of clarity, let's assume your people define the time of day according to which part of the horizon the Sun is at. So if the Sun is currently at 0°, it's 0:00, if the Sun is at 90°, it's 6:00, etc.
0° will likely be defined by some landmark. For example, the angle from the south pole to The Great Oak Forest might be 0°.
Time of Year defined.
Now, your people are going to realize that the stars visible at 0:00 will change over time. This will lead to the concept of a "star day", which is identical to our real-world notion of a year, without the seasonal variations. So maybe they define "January" as the month when the Gemini constellation is visible at 0:00, and "July" as the month when the Sagittarius constellation is visible at 0:00.
Originally, I thought there was a way to determine longitude from time of year, but I don't think that's accurate. Still, knowing which constellations are "equatorial constellations" allows your sailors to find the time of day even at night. Additionally, knowing the time of year can help keep local clocks accurate over long voyages.
Long-distance Time-keeping.
In order to find longitude, your sailors will need to know the current time relative to some known longitude. Generally, they'll probably compare local time to the time at the south pole, which we'll call "proper time".
With advanced satellites, they can use some kind of GPS, which would obviously also give them exact coordinates directly.
With basic radio technology, they can use radio stations to broadcast the current time. As the people expand their reach, then can have repeater stations set up so station A broadcasts every so often (say, every five minutes). Near the edge of A's broadcast radius, you have stations B, C, D, etc. around the ring. Each of them keeps a clock in sync with station A's broadcast, then broadcasts on a second frequency. Another ring of stations listens to the second frequency to sync their clocks and broadcasts on a third frequency. Etc.
With less advanced technology, your sailors will have to rely on simpler methods of time-keeping. Water-clocks, wound-spring clocks, etc. will all work to varying degrees of precision. Each port will be able to maintain an accurate clock, and the ships will re-sync their clocks accordingly.
I'm not sure what kind of accuracy they have, but numerous methods of determining time using other astronomical objects have been devised throughout the ages. Essentially, by accurately measuring various astronomical periods, such as the Moon's orbit around Earth, sailors can determine the current time by measuring relative motion of astronomical objects, such as comparing the Moon's position to the background constellations.2
Putting this together.
From here, they can combine three pieces of angular information to know where they are on the globe.3 4
First, they track the height of the Sun at noon. On the poles, the Sun will always be on the horizon. At the equator, the Sun will pass directly overhead (called the "zenith"). At any latitude in between, the Sun's height at noon will directly correspond with that latitude. From here, they can directly calculate their current latitude.
Second, they track the direction of the Sun's apparent motion. In the north hemisphere, the Sun appears to travel left-to-right. In the south hemisphere, it travels right-to-left. Combined with the above, this gives your people their exact latitude above or below the equator.
Third, they track the angular difference of an accurate clock between "proper" noon and local noon. This will be easier as they develop radio then satellite technologies, but can still be done with any kind of local clock. This angular difference gives the longitudinal difference between where they're at and some prime meridian.
Fourth, they can track various angles to or between astronomical objects, which may be helpful in more accurate time-keeping, but isn't directly helpful in determining position.
A note about the Sun's angle near the pole.
If you're extremely near the pole, and on or surrounded by land, it's possible the Sun will always be below the horizon, making it impossible to measure the Sun's angle at local noon. This would, in turn, make it impossible to know your precise latitude (and further, hard or impossible to know your precise longitude since you couldn't determine the exact proper time of local noon).
Note, however, that this is not likely to be a huge deal anyway. If you're on land, you can use landmarks to find your way pretty easily to begin with. It's really only when you're on the ocean that you'd have a really hard time finding your bearings. And on the ocean, the Sun will always be above the horizon at noon.
Regardless, I did some math. Let's say you're standing at sea level, and the horizon is covered by hills the height of Mt. Everest (about 5.5 miles in elevation). The angular height of the hills relative to the horizon is given by
$atan(\frac{5.498\text{ mi}}{X\text{ mi}})$
where X is the distance to the hills.
The latitude difference between you and the hills is given by
$\frac{X\text{ mi}}{24901\text{ mi (Earth circumference)}}\cdot 360°$.
Because the Sun's height at noon is equal to your latitude, we can set the above equations to equal each other and solve for X. This will give us the distance from the pole where Mt. Everest would prevent the Sun from rising.
I'm having trouble getting WolframAlpha to solve the equation directly, but my graphing calculator gives an answer of $X=\pm 147.578 mi$, which gives angles of 2.134° for both occluding height5 and latitude6.
Because the viewer is 147 miles from the pole, and the giant mountains are 147 miles from the viewer, this means anyone within 295 miles of the pole will never see the Sun.
Realistically though, you're not going to have a horizon full of Mt. Everest-sized hills while at sea level. Which means the occluding distance will be much smaller. Doing the same math for an elevation of 1320 ft gives a 63-mile occlusion radius, and an elevation of 500 ft gives a 39-mile radius.
In general, the more bumpy the terrain, the more likely it is that you've got a huge cliff between you and the horizon. But it also means you don't have to walk as far out of your way to get a better view.
So even at distances much closer than 300 miles from the pole, there's a good chance you could use the Sun's position at noon to get your current latitude (and, with good time-keeping, your current longitude, since you know the proper time of local noon). By deliberately using a route that keeps you at higher elevations, you could maintain an accurate log of your position throughout most of your trip.
