The free online lessons
I can't stress they're free, enough. These lessons are geared towards the serious learner, there is no cutting corners here. The online lessons teach you Japanese the way it's taught in universities, only for free. This has obvious advantages, as well as disadvantages, but the most important thing is that you can get your learn on.
The site is still in its migratory phase, so not all of the lessons have been ported yet, I will get them online and up to date as soon as possible (although if you want to help out, give me a shout!). For now, the prelessons and lesson 1 are online, and lessons 2 through 4 are in the process of being ported from the old site to their new dokuwiki repository at lessons.nihongoresources.com.
You need to know the kana if you want to take these lessons, so if you don't: hit up the hiragana and katakana sections, which will teach you how to read and write the kana characters. The real lessons use a mix of kanji and kana only, no romaji, so you get the most out of the lesson if you write down the sentences while you go through the lessons to get a feel for Japanese sentences.
You're going to get as much out of these lessons as you put in, so I recommend not just sitting there and reading: write along with it and get that learn on! You may also like to download a copy of the free NR grammar book (a bit over 400 pages) which covers all the topics from the lessons in a nicely topicised manner, so you can look up how the book explains certain concepts, should the lessons leave you curious.