Ulan Bator or Ulaanbaatar is the capital of Mongolia.
At the bus station you'll find people trying to fill up their cars with passengers. If you're lucky they won't be able to, and will take you for free. Or you can buy a bus ticket to the first town (but buy early and make sure you have a seat or you'll be sitting on the floor).
To the North and West (Russia, Darkhan, Arvaikheer etc.)
Take bus #17 (or #17b if not mistaken) from the center to a certain bus stop after 5-Shar (see map). Walk across the railway line and hitch.
To the East and South (China etc.)
Take bus XO to Khuzhirbulgan (and I guess the one to Nalaikh also goes that way, but it continues where the other one turns left) from the square to the East until the bus turns off Peace Avenue to the left.
Nomadwiki & Trashwiki