Tae Kim over at guidetojapanese.org has some interesting things to say about learning kanji.  It’s well worth reading the whole post, if not his entire blog.  Here is what he says about memorizing on and kun readings for every kanji

To put it bluntly, learning all the readings of a Kanji is a complete waste of time. Yes, as a general rule of thumb, Kanji compounds use the on-reading while single characters use the kun-reading. However, this rule is nowhere consistent enough to make it more than a good guess (this is particularly true for 大 which we can’t seem to decide to read as おお or だい).

In addition, many Kanji have multiple readings kun or on-readings such as 怪力(かいりき or かいりょく?), 外道(げどう or がいどう?), or 家路(いえじ、うちじ、やじ?). Even if you guessed the correct reading, it might be voiced or shortened such as 活発 and 発展. Also, Kanji such as 生 have so many readings, it’s completely pointless to memorize them because you won’t know which one will be used in a word such as 芝生、生ビール、生粋、and 生涯. Not to mention the various words that only use the Kanji for the meaning while completely ignoring the reading. These words such as 仲人、素人、and お土産 are literally impossible to guess the readings for. At the end of the day, if you see a new word, you always want to look up the reading to make sure you learn the correct combination. In addition, the readings will be easier to remember in context of real words that you can actually use. Essentially, memorizing the readings by themselves is a complete waste of time.

His suggestion (as mine) is to learn kanji meanings, stroke order and to learn lots and lots of vocabulary.