A fantastic book for learning Kanji is "Remembering the Kanji", by James Heisig.[1] It teaches you the meaning and writing of each character independent of its Japanese readings, which drastically reduces the cognitive load of memorization. It also arranges the characters in a logical order to speed up the process. A few months of study with this book are enough to memorize the reading and meaning of the 2136 jouyou kanji. These are the basic characters you need for proficiency; Japanese students learn them during elementary and middle school.
(A personal anecdote: I used this book one summer to learn and remember about 1500, substantially more than I could use after 6 years of studying Japanese and drilling kanji the usual way.)
If this sounds too good to be true, it's partially because it is. You won't learn much actual Japanese by studying the characters; you'll just learn to associate them with English words. This might be frustrating initially, but if you're committed to becoming proficient in Japanese this will speed up the path substantially. If you've ever seen how quickly native Chinese speakers pick up Japanese, you'll understand why: the Chinese and Japanese languages have about as much relation as Japanese and English. The advantage of the Chinese speakers is that they already know all the Kanji in their native tongue.
I believe that a serious study of kanji (such as Heisig) is best left for a more advanced level of Japanese. Beginners often overload themselves trying to learn thousands of kanji when they don't even know the meanings of the compounds that the kanji are used in. I believe that Heisig even mentions in his introduction something to the effect that using his book won't really improve your Japanese, it will just improve your ability to learn Japanese. Rather than spend hours per day studying Heisig for months, I would recommend a more traditional approach to beginners of learning the most common kanji as they learn the vocabulary.
For the advanced student looking to master kanji, then a method like Heisig's seems best. However, for those interested in the Heisig method, I recommend this book: Kanji ABC [1]. It is similar to Heisig's but organizes the kanji so that you learn similar kanji together. Also, while Heisig spends much time trying to get you to memorize convoluted association sentences, Kanji ABC simply gives you the radicals (similar to Heisig's 'primitives') and you build your own association sentences.
I think you need to be a bit clearer about what you actually learn via Heisig - it's not accurate to say you're learning the meaning of kanji (which have several meanings depending on how they're compounded or not with other kanji), which you're not actually. And my understanding was that you don't learn the readings either. I could be wrong on that but learning all the readings for a kanji is a terrible approach. Much better to learn them by way of learning vocabulary.
Heisig seems to be best as a way just to get all the kanji into your mind as opaque artifacts, just a visual familiarity primarily. Which can be a huge help when you actually start learning Japanese.
(A personal anecdote: I used this book one summer to learn and remember about 1500, substantially more than I could use after 6 years of studying Japanese and drilling kanji the usual way.)
If this sounds too good to be true, it's partially because it is. You won't learn much actual Japanese by studying the characters; you'll just learn to associate them with English words. This might be frustrating initially, but if you're committed to becoming proficient in Japanese this will speed up the path substantially. If you've ever seen how quickly native Chinese speakers pick up Japanese, you'll understand why: the Chinese and Japanese languages have about as much relation as Japanese and English. The advantage of the Chinese speakers is that they already know all the Kanji in their native tongue.
[1] http://www.amazon.com/Remembering-Kanji-Complete-Japanese-Ch...