The first thing you need is a little knowledge about the radicals. If you can break a kanji down into it's radicals, you can look it up in books and electronic dictionaries. It makes it easier to understand the kanji too, since you can identify its parts. If you can name a few of them, you can often type the names into an electronic dictionary to filter choices. Here's a couple of places to learn:
Names of many radicals: http://japanese.about.com/library/weekly/aa070101a.htm
Radicals by stroke count: http://nuthatch.com/kanji/demo/radicals.html
A dictionary lookup with radicals: http://jisho.org/kanji/radicals/
The next thing you need is to know about stroke order. Learn the general rules, like write left-to-right, and how a horizontal, then vertical stroke count as one (like in 口, which has 3 strokes, not 4). You can learn most of these rules by learning the first 30 or so basic kanji.
With these two things, you're ready to look up kanji in a book, but it is tedious doing it that way. Instead of this, find a touch-screen device and get some software for it. Nintendo makes a good dictionary for DS, and iPhones or iPads work well.
With iPhones, iPads (and even the touchpad on a newer MacBook) you can write in Chinese characters, but they still don't have support for Japanese kanji. Plenty of the Chinese characters are the same as Japanese kanji, but there are enough differences to make you confused. Find an app with a custom input method instead. I use Daijirin to write in kanji, and it has a custom input method. After I find it, I either search in that app, or copy and paste into another app.