I've been self-studying Japanese for a year now and I'm more than satisfied with my progress so far.
What things I'd recomend after a year of learning:
1. First of everthing, learn the kana (Hiragana and Katakana). Be sure to spend at least a couple of weeks to make sure you remember them. You can find free aids for your cellphone.
2. Start the excellent downloadable japanese lessons w/audio from NHK. Listen (and read) each lesson several times before advancing to the next one. www nhk.or.jp/lesson. Hear them until you can understand everything what's been said, it's full of everyday sentences. JapanesePod101 is good also but it's audio is not as good (at least the first lessons) and there's no follow up history that get you hooked.
3. Study grammar. Then try to understand the grammar in the sentences you are learning. Wikipedia is good, but short. You can complete with www timwerx.net/home/index.htm, which I like specially the verbs part for it's lenght. It's fully in romaji, though.
Just keep in mind that (like in english) some sencences just are the way they are. They are fixed ones, period, there's nothing to understand there.
4. Start slowly but stubbornly to learn the kanji. Again, there's tons of free cellphone aids for this. I'd recommend learning them in two stages, first the meanings, then the pronunciations (no more than 3/4 per kanji, or you'll get tired of your progress). To give you an idea, I have so far learnt ~500 kanji meanings (~ of the official 2200 for reading the newspaper), but only ~300 pronounciations.
For memorizing them, I'd recommend this site www kanji.koohii.com, related to the famous book "Remembering the Kanji" from James W. Heisig (It's better if you buy it).
They have good stories that help put them in your head.
The one thing I don't agree with is the order for learning them, I first learnt kanjis from grade 1 and 2 and some grade 3 (first's years of japanese primary school), as they are the more frequently used. I don't know if I did good or not in doing so, but It served my needs, now I felt the need to change and I'm doing their regular order.
Excellent on-line dictionary: tangorin.com. You can search kanjis by its parts.