Here are some notes from traveller George, who travelled to 
Kyzyl in the early summer of 2011.
I arrived to Krasnoyarsk by train (~3500 rub platskart from 
Kazahn). There I used couchsurfing for accommodation, but I got a very good 
impression and help from Kiwi hostel: http://kiwihostel.ru/index.php/en/ . Sayan 
Ring ( http://www.sayanring.com/ ) was also very keen on helping me, providing 
services for transportation, accommodation and others.
To get to Kyzyl from Krasnoyarsk there are the options to take a 
direct bus, or a train to Abakan and then a train to Kyzyl (you may get in touch 
with Sayan Ring travel for detailed information). Instead of these, I used a 
shared van ride (marshrutka) to get directly to Kyzyl. This takes about 12 hours 
(including short stops for food and rest) and costs 1700 rub. This is a regular 
service, leaving on specific hours (not every day, as far as I understood) at 
about 3-5pm both from Kyzyl and Krasnoyarsk. The driver drops you off in the 
place you ask him when you arrive. In case you need some phone numbers I 
happened to use:  89231845555, 89233074744, 83942251454. All vans leave from 
Krasnoyarsk in "china-town"= Kitay-gorod, and from Kyzyl from the town's central 
Bazaar (near the city's central square, where the theater is). It is recommended 
to call them earlier to book, or visit them from morning-noon to arrange 
everything. They ask you to be there one hour earlier.
In Kyzyl I also used couchsurfing to find accommodation and 
happened to work out really well! Then, after getting back to Krasnoyarsk, I 
flew back to Moscow using UT-air for ~10000 rub.
Best regards,
George
PS: Many greetings to Kiwi hostel and Katerina from Sayan Ring!