Train from Beijing
There are three train options to get from Beijing to Ulaanbtaar, or UB, as everyone calls it. The cheapest way is to catch local trains up to the Chinese border town of Er Lian, then cross the border in a bus/minivan, then catch a local train from the Mongolian border town of Zamyn-Uud to UB. However, this is a real hassle to do if you don't speak Chinese or Mongolian, particularly as you cannot pre-book normal Chinese trains without a Chinese bank card, and you cannot pre-book Mongolian trains online at all. If you do want to take this option, I'd recommend getting in touch with the guys at China DIY Travel (www.china-diy-travel.com), a trustworthy Australian-run train ticket agency who will be able to help you get to the Chinese border. From there, though, you'll have to sort everything out on your own (ie cross the border, and buy a train ticket to UB). Given your timeframes, I don't recommend this.
The other two options are the two direct trains which run on the Trans-Mongolian section of the Trans-Siberian Railway network. One of these trains is the K3. This leaves Beijing every Wednesday at 11.22am, and arrives in UB at 2.20pm on Thursday.
The other train is the K23. This leaves Beijing every Tuesday (and sometimes also every Saturday) at 11.22am, and arrives in UB at 2.20pm on Wednesday (and sometimes Sunday).
Unless you go through a special Trans-Siberian travel agent (Monkey Business - www.monkeyshrine.com - is one in Beijing that I can recommend), which will obviously cost a lot more, then you will have to buy your tickets for either of these two trains in person in Beijing from a special branch of CITS (China International Travel Service). The branch you need to go to is five-minutes walk north of Beijing Train Station (where both trains leave from).
Tickets are easy to come by, so you'll be fine simply buying these tickets when you arrive in Beijing. Just make sure you buy them as soon as you arrive (ie before you head off to the Great Wall).
The CITS office is open 9am to 5pm Monday to Friday and 9am to noon on Saturday and Sunday. It's housed round the back of the lefthand side of the lobby of the Beijing International Hotel (北京国际饭店; Beijing Gwor-jee Fandian). The CITS office telephone number is 6512 0507. They speak some English in this office, but note; you will have to pay in Chinese cash.
Here's a map for the Beijing International Hotel:
Trains tickets to UB cost as follows:
Hard Sleeper (4-berth): ¥1584
Soft Sleeper (4-berth): ¥2137
Deluxe (2-berth): ¥2311
The hard sleeper tickets are best value and, despite the name, they are very comfortable (they are not literally "hard"!).
Terelj National Park
You will be spending your time in Mongolia in Terelj National Park, a huge national park with seemingly endless grassland hills - perfect for horse riding - cut through by rivers and streams. It's a great place for camping, if you have your own equipment. But if not, there are dozens of tourist ger camps you can stay at. The one I've recommended (Ecotourism Ger Camp) is quite deep into the park, and quite a hike from any roads or villages, so it's lovely and peaceful without being ridiculously remote.
I can't find a photo of Ecotourism Ger Camp, but here's one of another camp in Terelj National Park, just to give you an idea:
Hopefully by the time you arrive in UB you will have already been in touch with Bert, the Dutch guy who runs Ecotourism Ger Camp. With a bit of luck you might be able to catch the 4pm bus from UB straight to Terelj (see the 'Stay' section for bus details). Alternatively, he might be able to help you arrange a private car to take you out there. A third option would be to spend one night in UB and then catch the noon bus to Terelj the following day.
I'd recommend spending at least two nights with Bert so that you have at least one full day in the park to do a decent horse trek.. but obviously this is up to you. Email Bert and see what he recommends.
If you want to spend more time in the region, and are looking for something a bit different to do, you could also consider a rafting trip. These tend to cost around US$50 per day, so if that's within your budget then consider contacting Nomadic Journeys (www.nomadicjourneys.com), a well-run Swedish-Mongolian outfit which does rafting trips on Tuul Gol (a river which traverses Terelj National Park).
Bert may also have information about rafting trips, so it might be worth asking him.
Although you'll hopefully be spending most of your time in Terelj National Park, you will obviously have to spend some time in UB. Here's a map pinpointing the key places I've mentioned in this section of the itinerary, including all three guesthouse recommendations, both restaurant recommendations and the railway station and international railway ticket office:
For potential places to stay in UB, see the 'Stay' section.
If, for what ever reason, you cannot get hold of Bert, and you do not end up making it to Eco Tourism Camp, then ask at your guesthouse in UB about a possible trip to Terelj National Park. Most UB guesthouses run day trips and/or overnight trips to Terelj, so, as a last resort, you will be able to arrange something through them.
For food in UB, I'd recommend Luna Blanca, famous for being Mongolia's first-ever fully vegan restaurant. It's clean, healthy and great value. And also very central.
Loving Hut is another decent vegan option nearby.
For train tickets to Irkutsk, your guesthouse in UB may be able to help. Otherwise, you need to go to the International Railway Ticketing Office, which is near the train station (but not actually at the train station). Come out of the train station, cross the road and turn left, then walk between two buildings on your right to find the yellow-painted ticket office set back from the main road. It has an English sign on it. You'll need your passport (with the relevant visa in it) and Mongolian cash to buy tickets here. It's open from 8am to 8pm.
As far as I know, there's a daily train from UB to Irkutsk. Train number 263. It leaves at 9.10pm every day and takes 36 hours. But make sure you double check this when you get to UB as train schedules do change.