Dealing with water in the desert was typically handled one of two ways. Contrary to popular belief, locomotives didn't have to stop as frequently as you might expect. On average, locomotives would stop about every 90 miles or so. Sooner if they were working hard grades and such. Larger locomotives could go longer, but the average would be 90. So I'll go with that.
Basically, every 90 miles or so, there would be a water tower. What's more, railroads tended to put towers at stations, so it wasn't uncommon for a train that had to stop anyway to go ahead and top off their water. In the desert though, the companies had a handful of ways to deal with it. ATSF, SP, and UP would often set up large "tanks" which fed a particular tower. These worked off of very deep wells. Where that wasn't possible, they also used tanked in water carried in specially designated tank cars that would be dropped off every day or so by through freights. These tank cars were used to refill the water towers. Generally speaking, railroads didn't like to do this with a water tower that saw a great deal of use, so you'd often see this on outlying towers that didn't have a ready source of water handy. Since only the locomotives with the smallest tenders used those towers, it was something of a cost effective measure to deal with the situation.
As tenders got larger and locomotives could go further with one tender of water, railroads started doing away with these outlying towers, and instead requiring stopping trains (such as locals) to fill up every station stop. This could be every 20 miles or so, but the general idea was that the tender didn't ever run dry.