I can't tell you what Japanese people do, but I found that I need to learn actual words (at least two, preferably three or more) with a particular Kanji before I can reliably remember the ON-reading. Also, I try to group Kanji with the same 'phonetic' compound together, i.e. 生性星青晴情 'sei'. That doesn't work always, there are still irregularities (e.g. 各格 'kaku', but 絡洛落 'raku', and there's 'kyaku' and 'ryaku', too), but it helps. http://www.genetickanji.com/ is a nice site for learning Kanji in a sensible order (simpler elements first).

小学校で漢字をたくさんノートに書いて覚えました。 音読みはだいたい熟語で覚えます。 基本を覚えるとパターンが見えてきます。 「懸は県が入ってるから同じ読み」のように難しい漢字を音読みで簡単に読めます。