Getting there and away, Getting around
You can cross the border by any transport means (but not by feet) at Erlian/Samiin Uud at the south and Ulan Ude in the north. There are some other border crossings, but mostly you need special permits to get there and a second permit to cross the border as a foreigher to China and Russia. In Bayan Olgii there is a bus connection to Almaty in Kasakhstan, but until now it is not clear if a Non-resident of these countries can cross the border to China, for making it to Almaty.
Getting there by air:
Aeroflot has a daily connection to Moscow, Miat flies 2 times a week to Berlin, Korean Air at least once a week to Seoul and China air some times a week to Beijing. If you speak some mongolian you may try out the special discounts of miat.mn, which are offered only in mongolian language. Nevertheless you can book it.
You have at least 2 times a week regular flight connections from Ulan Bataar to the Aimag capitals: Bayanhongor, Khovd, Bayan Olgii, Altai, Dalanzadgad and to some other cities. The tickets can be obtained at one of the many ticket agencies.
In Mongolia you have daily trains leaving to the northern and to the southern border, stopping at every smaller station. There is a west track from UB to Erdenet, on a daily basis. Other destinations can be reached by train but only one or two days a week and these destinations are some smaller side tracks from the main track. The actual schedule can be checked at the train station of Ulan Bataar.
Two times a week you have a direct connection to Beijing, and nearly daily connection to Irkutsk. 2 times a week there is the train to Moscow. Tickets to China must be bought in advance, and often they are sold out. In that case you may try the tourist wagon or a bus connection which is also available. The train to Russia are easier to get. In Irkutsk are passing by several trains for Moscow or Vladivostok.
In summertimes there some extra tourist wagons (for China ) which will end in Erlian, the customs and passport procedure is done in the train.
You may hire a bus with a group for reasonable prices in one of the countless guesthouses situated in the inner city. So you may get a first impression of the countryside. For example the Terelj trip which you can do at one or two days with the possibility to spend a night in a nomads tent, a Ger. There are also lot of other ininaries, mostly heading to the south for 5, 7 or 10 days. Other trips aren't offered, if you plan such a trip you have to pay the bus as an individial.
Mongolia has also a kind of public transport system. But don't expect a precise schedule, air conditioned luxury busses and any kind of comfort. At the western end of the Peace avenue you find countless small 4x4 busses to most of the aimag centers and some of the bigger cities. Usually the busses have a far destination like Khovd or Bayan Olgii, but in fact they do only one city a day. If some passengers leave in a city you may have to wait until the bus is full again, and this can last for some hours up to some days. Specially at the remote cities like Altai or Uliastai you may have to wait longer. Also be aware that you may count 11 passenger seats, but 20 passengers.
The most frequented road to the west is UB - Arvaikheer - Uliastai - Khovd - Bayan Olgii. In summer 2007 the average price for a day's trip was 18.000 Tugrik, but this may depend on the fuel price and the distance. At least you should be able to read the cyrillic destination to find the right bus. IMO the overland bus travel is the best way to meet people, because nearly all Mongolians travels that way.
There is also a south route to the west, but much less frequented: UB - Bayanhongor - Altai - Khovd - Bayan Olgii.
The third frequented destination is Murun, for passengers going to Lake Khovsgol. This destination can also be reached over Erdenet. From these Aimag centers or important cities you may find jeeps or busses to the smaller cities nearby, but to do a rare trip like Murun-Uliastai you need great luck. In general the driver stop frequently for having a meal or a small rest.
By law is nearly impossible to borrow a car, and without a residence in Mongolia you can not buy and register an used car for yourself. If you have brought a car, be aware of the street condition, specially in winter and springtime. But it's a good idea to think about it, because you can sell later such an used car in UB at good prices.
For overland travel you should consider this:
There are only some roads which could be driven by street cars. The main road from the north to the south. Should be paved completely, and streets within a circle of 100 km around UB are paved. A new road head for Kharhorin (Karakorum) to UB and a construction for Bayanhongor is in progress. Also the road to Arvaiheer is not too bad.
Everything else requires a jeep and a lot of driving and mechanics skills. Nowadays GPS becomes more common, and can be a great help for orientation inside of the country
This is possible, if you bring your own bike. For remote trips you should bring only the best, you need also aditional fuel tanks, and spare parts because a great part of the country is wilderness. Take special care because the fuel quality is leaded at 75 octane. In some stations you may get super fuel at 92 octan, and some machines need a reprogramming of the electronics to be able to consume such kind of fuel. Unleaded fuel is available only in UB. Fuel stations are very rare on the countryside, and you cannot expect any kind of technical help. That must be considered, specially of having a range of 500 km at least. But running out of fuel is not end of the trip, several truck or jeep drivers will sell you some litres if you are in an emergency.
It is possible to do some canooing on the greater lakes, but so long Mongolia hasn't any great rivers exept the one river which feeds the lake Khovsgol there is no boat transport.
You may try this, but be aware that between the comfort in a drivers cabin shared only with the driver and a seat?stand?place? at the back is a great difference. E.g. fuel trucks will go everywhere into the country, but they are very slow on bad road conditions. Can be very funny, or very exhausting.
Probably the greatest challenge - bicycle trips to the countryside. Near the state theatre is the 7 summits store which offers all you need, at a good quality, at western prices or more. Although mountain bikes can be bought on any bigger market you cannot just buy a bicycle - without spare parts you may get into trouble very fast. On the countryside spare parts can be obtained only by taking apart one new bike at the aimag or sum capital markets.... and there you can also having fixed holes in tyre tubes. After the end of the paved roady you may make 30 - 50 km a day, maybe more. Provisions are available only in the cities, otherwise you have to depend on the hospitality of the families which you will meet on the countryside. In the southern part of the country water provisions are important because settlements of people (for water) are very rare, and it could happen that you need two days from one water source to another.
So a bike, a trip and the equipment must be chosen by great care, and you have to be in a top condition.