I did (Kyoto)-Beijing-Moscow-(Stockholm) last december.
In Russia we travelled mostly on domestic trains of various kinds (the Trans-Mongolian have some russian cars attached in Russia which allow domestic travel), using mostly "Kupe" 4-bed compartments. We made most planning and booking as we travelled.
We used the RZD web booking at http://pass.rzd.ru/main-pass/public/en and selected "ticket for own printing" (using internet and printing at the hostels). In most cases this paper is valid as a ticket when entering the train. In some cases you have to exchange it for a paper ticket, it's clearly written in english. You can then use the booking code in either the ticket vending machines, or just show it at the counter (worked best for us). Neither step needed any real Russian language skills.
Availibility : We never had any problems with availability. If you go with the domestic trains, and even more going east-west and outside summer there ought not to be any problems. RZD prices are fixed for a given day, but prices varies with the calender day (irregardless of booking pressure) and can be +20% in summer and before christmas, -5% in november and up to -20% some days in march.
Price : This was actually AFAIK the cheapest way of going. Total price for Japan-Sweden was about 700 Euro including Chinese tickets, two ferry connections, and the fact that we travelled "Kupe" in both Russia and China.
Border crossing : We travelled the trans-Machurian to Manshouli and the from russian Zabaikalsk around 10 km away. This allowed us to use domestic tickets only. Crossing the border can/should be done using bus or taxi (we tried on folding bikes which was an adventure of bureaucracy).
If you wish to go by train across the border you have to use an agency, for example Real Russia (which is also good for overview planning in any case)
China : We bought tickets for china from http://china-diy-travel.com/, a low-overhead travel agency for travellers who can do some planning on their own. They have all instructions for train travel in China and was quite fast, helpful and friendly - just try to keep in mind that they are a ticket agency - not tourist information and "all-inclusive" agency.
Stations in China were a bit crowded and bureucratic, and you had to show your ticket 4-5 times to enter your train. That said, every train was on time, we got through all the gates and the 4-bed compartments were clean and calm.
Trains in Russia were more like Western Europe, you just had to show your ticket once; to the carriage attendant to enter the car. The toilets and cars were generally clean even on non-firmery train. Going "Platskarny" may be a bit more basic; expect sweaty soldiers on the way to/from military service and a bit more chaos; but probably OK and perhaps even fun for a backpacker.