We, Russian/Cyrillic typing people, are very unlucky with the stock Android keyboard. Android 2.1 went out without Cyrillic keyboard at all (fortunately there were third-party keyboards on the Market). Android 2.2 (FroYo) added Cyrillic keyboard, but without letter ъ (Cyrillic hardening sign). It was fixed in 2.2.1 update and well as in 2.3.
Now, when all the Cyrillic characters are here, the next problem is the absense of Russian dictionary (even in latest-and-greatest Android 2.3 aka Gingerbread). The thing is, when you type, Android keyboard suggests you correct words (to save a few keystrokes), and in some cases even correct mistyped words. It does so using a frequency list of words -- and there's no such list in Android for Russian language.
So I went ahead and created it. Well, technically speaking, I took the existing frequency list from here and wrote a small script to convert it to what appears to be Android format. Now I need to either figure out how to build a keyboard with this list, or ask someone to do it.
You can find both my script and the resulting list here: http://kir.sacred.ru/freq-dict-ru/
The biggest conversion issue was to convert frequencies from ipm (instances per million words) to values suitable for Android (1 to 255 range). I used double natural logarithm to smooth out the frequencies, and a dirty hack for the first few words to allow for more even distribution. I am not a mathematician so it might be all very wrong -- please correct me if you feel like it.