Learning Cyrillic is actually one of the easiest parts of learning Russian, I always say that and no-one believes me!

I learnt it almost "incidentally" myself, I started learning on livemocha, which doesn't even give lessons on Cyrillic, and simply picked it up from hearing the words pronounced, seeing them on the screen and gradually pairing up the sounds with the letters. I learnt most of the alphabet that way, but to polish up my knowledge I had to use a couple of other sites. Of course, initially you'll always have a few problems (mixing up «ч» with «у», or «б» with «в»), but these should iron out with practice.

I know this method works, because I started learning Greek on livemocha as well, and now I'm reasonably confident with the Greek alphabet too (although my knowledge of the Greek language remains very small).