12:26 p.m. on March 24, 2004 (EST)
As Brian said, no, you don't carry all the water with you. You plan your trip around the waterholes, and you do most of your hiking during the cool parts of the day. I got a lot of my knowledge of desert travel by growing up on an Indian reservation in a small village, where you were into the desert within a hundred meters of the house. I will admit I don't quite understand, as an adult, how we kids used to play hard, bicycle hard, run hard in 120+ deg F heat, but we did.
Anyway, first strategy if you are hiking in the March through November time frame is to start your hike before dawn and shelter by noon at the latest, then maybe some more hiking in the last hour before sunset. High desert, like Utah or northern NM, is a little different, since you dehydrate a bit more quickly at altitude, but basically the same idea. Another strategy is your clothing. This is the one place where cotton is good, since it holds water (your sweat) that can evaporate, providing cooling. The clothing should be loose, full coverage, and light color (look at Arabian robes, although as a kid we always wore jeans, which are pretty dark - loose jeans, not the painted on high fashion variety). Do have some warm clothes, though, since the temperature drop overnight is very large, due to the low humidity, sometimes 50 or 60 deg difference.
As Brian says, there are lots of water sources in the desert - springs, wells, rivers and streams, plus little potholes in the rocks and ways of getting water from the plant life. Plan to refill at every waterhole, since the next might be dry or a long way off. Well, there are fewer rivers these days, thanks to all the dam projects. Even by the time I was 10yo or so, the Gila River, about a mile from my house, was dry most of the year, except for flash floods. Oh, yeah, it does rain, especially during monsoon season (mid summer into early fall, in Arizona and New Mexico), so you can catch the water. One time we were backpacking in Bandelier and found one of our intended springs had dried up. We continued on to our intended campsite with diminishing water (we had filled up at the river - Bandelier borders the Rio Grande Gorge) and set up camp knowing the next water was a couple miles further on. The typical afternoon thunderstorm came up, so we set pots, water bottles, and all containers we had to capture the rain. That gave us several more liters in short order.
When you make your midday stop, set up a tarp to provide shade with ventilation, and pick your shelter site judiciously. Don't sit out in the sun. If possible, go with an experienced desert rat.
Obviously, the web is not the place to learn desert travel, but maybe these hints will help. The book Brian recommended is a good one, and there are others. If you can go with an experienced person, you will learn faster. Hey, if you go to Utah as you said, maybe you can get Brian to take you canyoning. He knows lots of good slots, er, spots, and spends a lot of time in Canyonlands, Arches, Brice, Zion, that area.