I wouldn't completely rule out learning to write kanji.
I think that the physical action of writing helps you remember and learn.
Also it can be satisfying in and of itself.
And it can be a useful skill so you are not stuck forever using romaji or kana to make handwritten notes.
That said if you are using a computer, reading (or recognising maybe) is the more immediate and useful skill.
I handwrite my classwork, usually needing two drafts to make it neat and get the unknown kanji shapes correct. I use furigana so I can read back what I've written. Eventually I don't need it and I look up kanji less often. Because it takes more effort, is active rather than passive and I look harder at the kanji, I think I remember more than when typing on a computer screen.
The type of stories that help me is using the kanji in example sentences, rather than making something up to remember the shape. Learning in the context of a sentence rather than in isolation. Learning a kanji as part of a compound rather than a single kanji. Understanding the actual components and derivation (rather than making up my own)
The more links you make in your brain the better.
I also find I seem to naturally learn to read a kanji by meaning then kunyomi then onyomi. Rarely all at once.
Learning how components and radicals work is useful. Helping you guess at partially remembered kanji. And also allowing you to use printed dictionaries.
If your listening skills are good, reading a kanji transcript along to an audio recording is a good excercise. Something like Miki-san's blog except slower maybe.
Use flash cards. Read things. Write things. Check your writing! Essentially repetition is the way to learn. If you can integrate it with your other Japanese studies so much the better.
I like Basic Kanji Book Vol1 and 2 by Chieko Kano et alia, Bonjinsha
http://www.amazon.com/Basic-Kanji-Book- ... 4893580914
(dollar price on Amazon looks high to me, it's only 2400 yen)
It's a fairly traditional approach that eases you into reading and writing kanji. Grouping kanji by topic or function at around 10 kanji per lesson. And I think it would be suitable for someone with a beginners knowledge of Japanese in terms of vocabulary and grammar.