A chance to wax lyrical and bore you all about Chinese and I missed it by going off camping in the sunshine for two weeks. Damn! Better late than never.

I only learned Mandarin, but my understanding is that Cantonese has more than four tones - about six or seven.

It is frequently possible to guess at the pronunciation of a Chinese character you have never seen before, especially when you see it in context - a sentence or such like. This is because you can tell which part of the character is the 'meaning' indicator and which is the 'sound' indicator. However, since pronunciation has changed over the centuries, the 'sound' indicator is only a rough guide to the modern pronunciation. So the character 'bai, 3rd tone, meaning white' is used as a sound indicator for words pronounced as bai, pai, pa and bo, all in various tones, in modern Chinese.
It's always worth a go - someone might understand you!

(Side note, the Japanese have both adopted Chinese characters to represent Japanese origin words and adopted Chinese words along with their character. So a single Chinese character usually has two totally different pronunciations in Japanese, one related to the Chinese and one 'native' Japanese. For example the season spring is 'chun' in Mandarin Chinese and the same character is pronounced either 'shun' or 'haru' in Japanese. Depending on the word / compound it's in.
This characteristic of Japanese is to me far far worse than any pronunciation problems with Chinese - Japanese has two pronunciations you can't be sure of from the look of the character instead of one....)

As for finding words in a Chinese dictionary, Bingley is half-right. NicholasW has a clue too.
The 'meaning part' is called a 'radical' and there are 216 of them, with a set order. Each has a number and a name. For example, number 86 (I think!) is a set of four dots, sometimes reduced to three in a set form, that is called the water radical. (A reasonable number of the radicals have two forms, depending on how much space the total character allows them to take up - just another thing you have to get used to. Different people write 'a' differently in English and we live with multiple forms.) The dictionary starts with Radical 1 as a standalone character. It continues to characters formed of Radical ONe plus one extra stroke, then characters formed of Radical One plus two strokes etc. When all the characters having Radical One have been listed, it moves on to Radical Two and so on and so on. Much like the alphabet really, except that you have to learn 216 radicals instead of 26 letters - and that it is not always obvious what the radical of a particular character is...
Dictionaries for foreigners are often arranged in some kind of phonetic order (bopomofo or Wade-Giles / Pinyin arranged according to the English alphabet) with an index of characters sorted by radical etc. This is because foreigners need to be able to look up a word by the way it sounds (if heard in speech) and by the character (if come across in writing). Kind dictionaries also have an index of 'Characters with obscure radicals' for when you have tried every element of the character you think could possibly be a radical and still got nowhere.

BTW bopomofo / bopomo is only used in Taiwan.
Also the PRC has simplified many characters and character elements to make them 'easier' to learn. They used common handwriting abbreviations - a bit like using the + sign instead of &, but even more so. Taiwanese and other overseas Chinese still use the full traditional characters in print. They tend to be able to understand simplified characters, as these are based on handwriting, but mainlanders, who have never seen the traditional characters, have real problems with them. At college we had to learn both, which was a real pain in the butt until we went to Taiwan and China and had to use both. I guess this is like knowing 'sweets' and 'lollies' as well as candy so that you can function in all (most? have I missed anyone out?) English-speaking countries.

...it's all a lot less random than it looks when you start out. And it really does get easier after a critical mass - 1-2000 characters and you know enough to start internalising the patterns.

PS NickW you're right about pinyin being non-phonetic on a letter-by-letter basis. I guess I never thought about it because I looked at it in the bopomofo way as an 'initial consonant' and a 'following vowel' (with or without nasal ending. From this cluster-by-cluster' point of view, it is phonetic. I think.