Navigation
There are a lot of options for navigation, but I suspect the real answer is to how to navigate is "all of these and then some".
Dead reckoning is maybe actually fine?
You know where you started, the direction you set out in, and the wind is "moderate and unvarying", so you can compensate in your calculations for an expected amount of drift. With all the "tattletales", you should be able to determine very reliably your heading relative to the wind - as well as its strength - since ones pointed upwind will read higher while one in the lee of the ship might even read negative. With enough sensors and knowledge of your ship's cross section from various angles, you could calculate the force applied on the ship, how it's resisted from the other direction, etc.
This could just be fine on its own, since the airship needs to go a couple thousand miles and end up within a couple hundred miles of some other point. We're trying to cross continents, not cities, so we just don't need that much precision.
Sun position based on polarization
Apparently:
According to the Rayleigh scattering theory, the polarization pattern of skylight is mainly determined by the solar position. Therefore the solar position can be retrieved by the polarization pattern of skylight. Based on this mechanism, the partially polarized skylight is utilized by kinds of creatures for navigation, such as ants, crickets, beetles, etc [2–8]. These creatures usually sense the scattering light of the whole sky dome or patches of the sky through their unique compound eyes and optic nerve systems, and then orientate their bodies according to the polarization patterns of skylight. It was reported that the Vikings (between AD 900 and AD 1200) used to orient during their sailings with the help of the “sun-stone”, which was applied to search the solar position by observing the skylight through the “sun-stone” [9,10]. The sun is usually blocked by the clouds and fogs, but the polarization map of the partly polarized skylight remains the same as in the clear sky.
Topography
Even a barren moon covered in sand is going to have some geography. If you know your own barometric altitude and can use radar or a rope with a weight to determine your altitude above ground level (AGL), you can develop a profile of the terrain.
- Sand constantly shifts, so it's hard to tell what the ground looks like? Carry around a small ground-penetrating radar rig that you can lower to the sand to measure the local bedrock topography.
Beacons of various kinds
They have sparse radio beacon towers laid out, with simple Morse code assignments. As these need maintenance and power, they don’t go far out into the desert and can only give approximations when between the five cities.
If we have constant and largely unvarying wind, it's going to be trivial to build plenty of wind-powered radio beacon nodes. A node could be composed of a 100-Watt (~1m / 3ft) micro wind turbine and a small transmitter hooked up to something that looks like the wheel inside a music box, and that's just if you don't want to have to invest in microchips for reasons.
- Including the panels, imagine something about the size of a desktop computer. Without them, there's no reason it would need to be larger than a Raspberry Pi.
- An airship at 5km altitude has a radio line of sight of 291km. That's without any ionospheric bouncing or anything, just line of sight VHF. Two wires can be used to give better accuracy, but a directional antenna (such as a dish, Moxon, yagi) could pin that signal down to easily within a few degrees.
- Sand gunks up the turbine? Use solar! Diffuse sunlight is still sunlight and the wind should keep the sand buildup to a minimum.
- Creatures attack them because they don't like the turbines/solar panels/hate EM waves? Use an aerostat! As a bonus, this lets the radio reach even farther. If you keep going higher, you're eventually describing our current GPS.
To top it off, radio waves on a barren planet without a bunch of noisy RF sources are going to go very far on very low power. Currently, there's a network of low-powered (~1W) beacons around the world called WSPRNet that transmit on HF bands and are regularly heard across oceans. Basically, any planet that can support people can have a sufficient radio beacon network good enough for "find the one city within a couple hundred miles".
Since your question implies a strong preference for some kind of wind-based navigation system, you might include some explanation for why this isn't done:
- Something - the pirates? sandworms? - actively hunts these beacons for nutrition/parts/to cause caravans to get lost.
- There's huge amounts of interference for some reason. Possibly the lack of a magnetosphere means the planet is constantly hit with various grades of solar flares or because the planet's sand and wind create a lot of electrostatic noise. Narratively, this could be fun because it means that it might be easier to navigate at night.
If radio isn't your jam, the beacons could use visible light (a lighthouse), masers, lasers, or even directed pulses of sound.
Seismometer
An airship could carry a couple of seismographs and land every so often to take measurements. I'm not familiar with the sensitivity of these, but I don't think it's crazy to think a a large underground community might well be detectable on seismographs for hundreds of miles without really trying, and could have a "thumper" to create regular impulses that could be detectable much further out. Particularly if there's not a molten core or mantle, I suspect seismographs would have work even better than normal, though deploying them on sand obviously isn't going to be great.
Rope or Chain
Each settlement has a "lifeline" that connects it to the nearest ~3 settlements. Depending on the tech level and context, maybe it's a giant optical fiber for data, maybe it carries power, or maybe it's nothing but a large rope that an airship attaches to for propulsion and navigation. Think an upside-down zipline.
There's precedent for things like this in the form of chain barges and I can imagine doing this so that the sandworms/whatever can't get to you, or because the sand doesn't bear loads well.
Other Stuff
- Sounding rockets that are fired off late at night at a known time that are visible for hundreds of miles.
- Plant and wildlife could vary significantly by latitude or longitude or maybe follow some known set of patterns.
- Wind could vary slightly in different places in a way that's recognizable. If the world is completely barren and has no geography, it should generally flow away from wherever the sun is centered.
- If the planet has any notable resources, maybe nodes of those resources are detectable by sight/radar/gravity sensors.
- There could be various anomalies that are used as waypoints. These might emit radio waves, sound, light, or draw animals to or away from them.
- No matter how much cloud cover there is, you should always be able to determine the position of the sun... it might just take more work and time. You might not be able to see the shadow cast by a gnomon with your eyes, but put the same thing on some barely photosensitive paper for half an hour and look for the arc that is less exposed than the rest.
- Clouds have a maximum height - they're made of stuff heavier than "empty" atmosphere, so send up an aerostat every so often to get a view of the sky.
- Some areas of the planet might have distinct smells or dust colors or chemical makeup or radiation.
Questions
And if I travel too high and out of sight of the ground, I have no reference at all.
... how do you get so high that you can't see the ground? Lift from aerofoils and lighter-than-air gases decreases as you go up, so a cargo airship isn't going to travel at high altitude without a very good reason.
A wire antenna can give a fair guess about what direction a given beacon is emitting from, but my personal experience with these on metal ships is they are wildly inaccurate, and can give you either the correct direction or the opposite of the correct direction. Quite easy to be completely spun around.
There's a process for dealing with that. If that were common, I don't think we'd have a network of over a thousand radio beacons in the US alone. I suspect your experience is because a single wire antenna is probably functioning as a dipole with the ship's body as the second pole. These have a two-lobed radiation pattern with two 180-degree opposed lobes which mostly explains your experience with wire antennas. See this image:

I have propulsion already figured out, it is beyond the scope of this question.
Not a question, just an aside: airships could anchor every so often and run their engines regeneratively to charge up batteries from wind power.
Mapping
The mapping system that you use might vary by community if one group prefers radio beacons while some other group prefers topography because they live near an extinct volcano.
If you're determined to have people yelling lots of wind-related words for guiding craft, I suspect you're going to end up with something akin to the points of sail. Regions would probably be named for whatever makes that area noticeable or distinct, while large tracts of completely identical geography and climate would probably be named as such: "the barrens" is generic while "equatorial dune zone" might be a formal name.
If nothing distinguishes one part of somewhere from other part, it'll just end up with no name, and people will latch onto whatever landmarks they can even if they end up exceedingly distant: "Bunkertown-Muskville Midway" might be an imaginary point halfway between those two towns. If you look at old maps, many had less a focus on the actual shape of the land and more of a focus on the distances between places and any landmarks you might encounter - often measured in transit time instead of physical distance. You can still see this in highway rest stops that have mileage charts:
. In your case, each city would be on the chart, along with any known landmarks as mentioned in the first section.