Moscow to Urumqi
By far the most popular route for travellers wishing to travel from mainland Europe into China and beyond is the Trans-Siberian Railway taking the appropriate route through Mongolia or the region once known as Manchuria. However, a less travelled but equally fascinating route is to travel from Moscow (Russia) to Urumqi (China) via Almaty (Kazakhstan). Because this journey is in no way as well documented as the Trans-Siberian equivalent, more research and preparation is required for a successful trip. However, the uncertainty attatched to the journey at times and the fact that certain levels of improvisation are required can give a far more rewarding travel experience.
Even though one of the most enjoyable aspects of a journey of this nature is the ability to be flexible in arrangements, a certain level of planning is recommended. Check train times beforehand so time wasted hanging around at railway stations is minimised. On lines from Europe to Russia, as well as from Russia to Almaty there are several trains a day, but train from Almaty to Urumqi goes only twice a week. http://www.poezda.net is an invaluable resource to travellers for this journey as well as many others as it provides acurate and up to date timetable information for all train routes travelling from, within, and to all former CIS countries.
The trains, ticket and reservation systems in CIS countries are similar as they share the common heritage from former Soviet Railways. The article Russian train travel gets you more detailed info.
Train tickets in Russia and CIS can be quickly sold out at peak dates (May–October), so don't expect that you always get a desired ticket on the day of departure. It is generally safe to buy it several days in advance. The tickets are available about 45 days before departure.
The European train reservation system is partly connected with CIS train reservation system. So it's possible to buy at European station an international ticket to any Russian and most of CIS cities, but berth reservations are often possible only to direct trains from Europe (mostly to Moscow, Saint Petersburg and Kiev). The berth reservation is almost always necessary, because Russian trains can ride through several days.
There are Ukrainian , Russian  and Kazakh  railway e-shops, but they are only in Russian and they do not accept many cards issued by non-CIS banks. They can offer international tickets starting in their country and with destination in other country. Apart from them, there are private agencies selling and sending Russian train tickets by post, but their prices are about 30–50% higher.
Currently there are no way to book a ticket from Almaty to Urumqi online. The Valentina's guesthouse http://valentina-gh.narod DOT ru/urumqi_train.html in Almaty can buy it for you with cca 20% surcharge, and you can pick up it at your arrival to Almaty.
It is vitally important to make sure all visa requirements are understood before travel. Obtaining visas at the last minute in countries other than that of your passport's origin can prove to be very expensive and not always possible. For this particular journey, it is likely a visa will be needed for Russia, Kazakhstan and China. If travelling by rail to Moscow from Western Europe, it may be most convenient to travel through Belarus. In this case, an additional visa will be required.
In addition to determining what countries will require visas, the catagory of visa required needs to be identified. Sometimes only a transit visa will be required but for longer stays in a particular country, a general tourist visa will be required. If travelling on a direct service from Moscow to Almaty, the train will in fact cross into Kazakhstan and back into Russia again momentarily before returning to Kazakhstan. Even though the border is crossed twice, only a SINGLE ENTRY visa is required.
Chinese embassies often require a onward and return air or train tickets, but you can try to ask for visa without it, only with itinerary of you trip in China. Presently (2010) it's not possible for foreigner to obtain a Chinese visa in Kazakhstan.
A final point of note, for stays of several days in Russia and Kazakhstan, any visas may have to be registered. This can be done at many travel agencies although embassies will be able to provide more information if required.