Dalanzadgad is the capital of Ömnögovi province (South Gobi). It is a rapidly growing town, due to the influx of business from Oyu Tolgoi mine, and the tourist attractions in the surrounding area. Although somewhat sprawling, it is easy to feel the Gobi encroaching upon you. Walk any direction for about 20 minutes and you are in the desert. Gurvan Saihan mountain range peers over the town from the west, and can act as a guide if you lose your bearings. With black smoke coming from the power station, and it's dust roads, it's not a very interesting town on its own, but it's a good place to stock up with food for your excursion into the desert. Although there is not much to do in Dalanzadgad itself, it is the jumping off point for the three main tourist attractions in the Gobi: Yoliin Am (Vulture's Mouth), Khongriin Els (Singing Dunes), and Bayanzag (Flaming Cliffs).
There is a pretty fast and efficient daily bus from Ulaanbaatar at 08:00 and 16:00 (about 12 hours, 27 500T). It leaves at the bus station which you can reach by the Electrobus #4.
Minibuses ("Porgons") leave from the Ulaanbaatar "Black Market" (Narantuul Zach) when they are full (that means, really full: 16 people!), usually in the afternoon between 12:00-17:00 and cost around 30.000T. Expect frequent breakdowns and up to 24h traveling time.
Flights are available from Ulaanbaatar too.
Yollin Am (Vulture's Mouth) is one of the three attractions of the South Gobi. It is only an hour's drive outside of DZ, though you must rent a private car. A day trip (at the time of writing; 2012) costs about 80,000 T. The canyon itself is gorgeous, and most of the year is covered with ice. Temperatures within the canyon will be significantly colder than the surrounding desert. Wear warm clothes. During tourist season you can ride a horse until the point where the canyon narrows and you must walk. If you continue to walk a mile or so the canyon will widen and you can hike up a large yellow plain on the right to get a good view of the desert.
There are a few good supermarkets in town.
Mazaalai Ger Camp, (North-East of Town). Probably the best address for independent travellers, this is a great place to hook up with the few fellow travelers to share a jeep into the desert. The friendly (french-speaking) owners can help you organize drivers. You sleep in a four-bed Ger. Great pizza and also a good place for a drink and a chat. 10.000T.
There is one daily bus to Ulaanbaatar at 08:00 (about 12h, 22.000T). It leaves at the North-East of town, just opposite of the Mazaalai Ger Camp and is probably the fastest overland option. Porgons to Ulaanbaatar leave from the market.