If you eliminate wheels, that leaves you with either skids, legs or hovering.
This option would include actual flat-bottomed boat hulls, catamaran like double or triple hulls and very wide and flat ski-like skids. The advantage of course is that it's very cool and like your desired sailing ship idea.
The major problems would be rocky/rough terrain and the very high friction, meaning you would need storm-like winds or unobtainium-plated friction-less surfaces to even get moving. I'd suggest using the skin of the enormous worms that live in the deep sands, but that's already been done...
Not just a few legs, but dozens and dozens of legs. Enough to make the crystal spider creatures green with envy. With the weight of the "ship" distributed over many broad feet, none of them would sink into the sand too much.
The major advantage is that the legs would work even on rocky and uneven terrain, where the skids would fail miserably. The disadvantages would be the maintenance on all those legs and relatively slow speed.
Here is some inspiration: windpowered beach walkers.
With Diesel Power(tm) at your disposal, a hovercraft may be possible, though it is unlikely that early generation diesel engines could produce enough power without becoming too heavy to lift. These would be very fast on flat and smooth surfaces like salt seas, but unable to handle inclines or rough terrain that the skirt would snag on.
The Best of Two Worlds
My recommendation would be a combination of legs and skids. The legs would have wide shields/skids along their length. On rough terrain it would walk centipede-like on all legs. On smooth sands most legs would fold into a horizontal position, putting the skids on the sand. The remaining vertical legs would push the "ship" forward in low-wind conditions (assuming some diesel power) or when going uphill.
When wind conditions are favorable, the upright legs are only required for steering (by creating drag on either side) as the "ship" goes into full sailing mode.
Why no Wheels?
For wheels, the short answer is: No rubber.
Leather (inflatable or not) wheels exist but they are unsuitable for large vehicles, since they're not strong enough to carry a heavy load and very vulnerable to sharp rocks and ridges hidden in the sand.
Wood is better and barrel-shaped wooden wheels with ridges or even paddles is probably the closest you'd get to desert driving. But without the flexibility of rubber, you'd have to "drive" very slowly or risk shattering wheels on impact with hard terrain features.
A tracked wheeled vehicle might do better, but there may not be enough metal available for solid metal tracks. Tracks with metal core links and bolt-on wooden components are likely to wear out and break at an unworkable rate, especially with sand getting in the links. Replacing a single skid or leg in the middle of the desert would be much quicker than trying to restore a broken track somewhere under the bottom of the vehicle.