In the English language, looking up a word in the dictionary is easy with only 26 possible letters, but how do the Japanese do it? Is there such a thing as a Japanese dictionary, and if so how would it work? Is there an alphabetical ordering of the 1000+ letter set in Japanese?
If I remember correctly, there is a set order for hiragana & katakana. Kanji is looked up by stroke number. I believe it works the same for Chinese (hanzi) and Korean (hangul) too.
Not Korean. Korean has a phonetic alphabet with a set order.
Sort answer: electronically. You had to know it was coming. 
For figuring out “what characters do I use to write a word I know”, I have to think it was the Japanese who invented predictive text entry because it’s a natural fit for the kanji entry problem. As mentioned before, Japanese does have two pure phonetic alphabets for text entry, sort of like our alphabet. From that point it’s a matter of entering “wa-ta-shi” in the text entry box, and magically watch the resultant character set change until you see the one you want.
For figuring out “what the hell is this hairy monster of a character”: A kanji character can be divided into 2 subcomponents. One is called the “radical” and one is called “the other pile of strokes”. The radical can be thought of as the “sorting part”, and there are something like 214 recognized radicals. So a kanji dictionary is organized into sections by radical (ordered by stroke count of the radical), then by the total stroke count in the first character, then by the stroke count of the next character, and so on.
So for example, when I pull out my kanji dictionary and flip to the first radical section, it starts with the first 2-character radical which is a smushed up version of 人. Then the first subsection of that one is where the second character of the word has 2 total strokes (there aren’t any 0 or 1 stroke forms in case you’re asking why I keep starting with the number 2). My dictionary doesn’t index by the 3rd or further character in a word; usually by the time you get down that far, you’re down to an eyeball scan of less than a dozen lines.
In closing, I’d also add that there are other sorting schemes than the one I described, and that I intentionally omitted some minor details to capture the general idea. If you really want to know the nuts and bolts of how this works, go buy your own 20-pound kanji dictionary and read the 50-page user’s manual that comes with it. But my advice is to go with a good handheld, preferably with character recognition, because it’s really a godsend for this task.
I’m not sure this paragraph is all that easy to understand. There are certainly 1-stroke radicals, and 1-stroke characters as well. The character for “one”, 一, being the most obvious example.
An important distinction, which has been hinted at by Silver Tyger Girl: there are two kinds of Japanese dictionary: a character dictionary, and a word dictionary. The character dictionary lists chinese characters (kanji) and is indexed by radical and stroke count. For instance, the character for “carp” is 鯉 and can be broken down as the radical 魚 and the body 里. The radical has 11 strokes and the body has 7 strokes. To look up the character, I go to the 11-stroke radical section, find 魚 and then head to the 7-stroke sub-section, where I should easily find 鯉. The character dictionary will list information such as pronunciation of the character, general meanings, sometimes etymology and words that start with the character.
Japanese, however, does not use only chinese characters but complements them with a native set of phonetic characters called kana. Each kana represents a syllable. In modern Japanese there are 46 kana and they are arranged according to a very logical sequence. A word dictionary is very much like an English dictionary: words are listed phonetically.
If you know how a word is read but don’t know how it’s written, you use the word dictionary. If you know the character but don’t know the reading, you use the character dictionary.
By the way, there are other systems for indexing chinese characters but they are essentially only used by foreign learners. Native readers only use the traditional, radical-based method.
Actually, Korean still uses Hanmun/Hanja on occasion and the system for looking them up in a Hanmun/Hanja dictionary is via radical order and stroke number.
For Japanese kanji, there is the traditional radical order & stroke number system for looking up kanji and the SKIP system for Kanji. For spelled-out words, there is a set order for the hirigana (the katakana order is the same). A number of my Japanese friends loved using the SKIP system and I was often lending them my SKIP dictionary.
The tricky thing for me when I was first learning Japanese was looking up words spelled out in hirigana. The words are listed in what’s known as their dictionary form. So, if you’re not conversant with the different verb forms or adjective forms, it could be confusing.
English is the same, though. I think any language that has inflections will cause some amount of hardship for beginners.
Actually, this is increasingly being the faster option, but for looking up kanji as well.
I will open handwriting tool in IME pad, and write the kanji, and then cut and paste into Microsoft Bookshelf, unless the unknown kanji is from and online article or an email. I then just cut and paste directly from the sourse into Bookshelf.