RE: Rivers in Arid Climates
Yes rivers exist.
No they are not those nice wide wet things you see in Europe (hence why explorers in Australia DIED... OFTEN).

Sandy rivers is your solution. They will run along normal river-paths, be filled with something like sand, tend to be surrounded by the only decent trees and periodically have little oasis-like pond/lakes. People from an arid climate will know where those run, how to identify them and know the solution is to basically dig down 5ft to find the water.

So is your map:
a) A satellite image or
b) A drawn map, to be held in the hand or stuck on the wall?

If it's a) then put in lines of half-dead green stuff where the rivers go.
If it's b) then mark them in, people will know where they are and as usual political boundaries will be influenced by them.


RE: Politics & Markers

Is it a Sat-Map or a Drawn/Made Map? I'll easily help you with "Made Map", ask the near-omniscient RobA or others about the Sat-Map style.

Nations are marked either by colours or icons. Old English maps mark the shires often with the Heraldic Marker. Tribes would have their own markers, just like Religions, Kings, Countries, Lawyers, Masons, etc, etc, etc.

Heraldry was used because it is simple, efficient, distinctive and can easily be recorded. The House of Lancaster uses a Rose, therefore people with a Lancaster Rose in their Heraldry will be Lancastrians... *ding*. "Hey that guy isn't a Royal, he can't use the Three Lions of Richard!" *nobles get ready to kill idiot*

I'd gun for Heraldry...