I have a country of desert nomads called Sahid, and the capital city is called 'Al'magor the wandering city.' This being literal, how would people be able to find this city easily? I have imagined the city crawling through the desert on stubby insect-like legs
Something the size of a city could be found by the devastation it leaves behind and the clouds of dust it lifts. Also it would be followed by their own inhabitants, scavenging wood, game, fruits, fish...
If not, just act like with any other animal: find the biggest source of water and sooner or later the city will need to come near it. Even a small city of a thousand people needs a lot of water each day just for drinking
Moving a city around just for the sake of moving it is a massive waste of resources. You haven't explained why the city needs to move, so let's assume it travels from oasis to oasis depending on the season.
Moving your city around isn't going to cheap. It will take a massive amount of energy. Whether it's magic or food or fuel, something is going to have to power the movement. Therefore, your city should always be taking the shortest possible route from one place to another.
As long as the destination is known, any resident of the city should be able to make a very good approximation of its location based on its known speed and its current route. For example, if your city is 5 days into the 20-day journey from A to B, you can estimate that it is 1/4th of the way from A to B along the standard travel route. With something that large, it doesn't even need to be a precise estimate.
If your city is wandering around aimlessly, it will be much harder to find. If the city is being moved around to hide it from attackers, the residents are probably doing their best to disguise its course, so the best solution would probably be prearranged meeting points (maybe it wanders aimlessly for 2 months and then makes a 3-day stop in Oasis A, so you just need to be in Oasis A during that 3-day stop).
If it isn't being moved for the sake of hiding it, the best solution is to use smoke signals. A pillar of smoke is visible for many miles and would make it easy for your nomads to relocate the city.
Perhaps the city moves in a predictable pattern. Maybe it follows the migration of certain animals. Maybe it just moves between oases that dry up and then it has to move to another to let them replenish. Or maybe it just follows a celestial cycle related to its cosmic masters.
If the wandering city is inhabited, perhaps the citizens send out messengers periodically to let the rest of the world know where it's heading. I mean, if it's the capital lots of people will be interested in where it is, and presumably it's not moving very fast. So, even transmitting information by the speed of horse and carrier pigeon, it should be possible to keep the city's general whereabouts known.
Also, smoke in the day and lights at night could make the city visible from a considerable distance even beyond the horizon, so seekers would only have to get within a few dozen miles to be sure of its location.
Related to Communication, perhaps the inhabitants can control or influence where it goes, and thus make a schedule which can be shared.
Seems like they can't find their capital city easily; this is why they are nomads...
More seriously, @Harabeck I think has the right idea, which is that the people in the city can be sending out messengers. The Mongols, famously nomadic, had a nice courier system that you could borrow: https://en.wikipedia.org/wiki/Yam_(route)
Your messengers could have established routes ... messenger X periodically goes to a given oasis. He tells everyone there the latest scoop on the city's location and vector and importantly, takes a bunch of homing pigeons back to the city. Then he can send word via pigeon until he runs out, as which point he goes back to the oasis for another batch.
Over time, these oases might become more important to the people than the nominal capital, because they're reliable. They stay where they belong, and you can always find them when you want them.