I studied Russian for several years, but it was at a university, so I don't have any recommendations about online courses.  I will say, though, that Max's comment makes some very good points.  Russian grammar is very different from English, and very complicated, and I think the suggestion of reading through a short grammar book before you actually start using the language is a good idea.  As Max says, you don't need to start memorizing grammar rules right away, but you should have a basic sense of how Russian grammar works, and how it differs from English.  After that, you can refer back to your grammar book when you've got questions.

I think finding some kind of structured course is a good idea.  Learning just from textbooks and recordings will probably work fine at the very beginner level (I've used a few different textbooks and haven't found any of them to be remarkably superior, or inferior, to the others), but you'll probably want at least some amount of feedback from a teacher or language partner once you get beyond very simple sentences.