I highly recommend the Genki series from Japan Times. This series is a pretty good introduction to Japanese grammar, gets you started with the writing systems (get away from romaji as quickly as possible, it's a terrible crutch that hobbles your literacy) and starts you off with a little vocabulary. There are accompanying exercise books with CDs if you want those too. I started learning Japanese through college courses, and these were our main text books in the beginning.
this is the version I used, and
this is the level 1 workbook.
This is the new version, looks like it comes with a CD and according to the reviews, addresses pretty much all the complaints people had about the first edition. I'd get this one if it were for me.
I used Genki I and II, and then their Intermediate Japanese book (which I dubbed "Genki III" because it was pretty much the same format with more advanced material). Later down the line, there are other books published by Japan Times that I found to be particularly invaluable. My favorite was
Cultural Episodes, which is just a compilation of increasingly difficult short essays that I found not only helped me step up my reading abilities, but they were also really informative and thought-provoking. When I finished it, I felt confident enough to start reading novels on my own.
When you're ready for it,
日本人の知らない日本語 (and
vol. 2) are really interesting, manga-style books written from the perspective of a Japanese teacher who learns more about her own language through her foreign students' questions.