Tonal languages seem exotic to most English speakers - not only is English not tonal, but very few familiar languages are; nevertheless, around half of the world's languages are tonal. While any unfamiliar feature in a foreign language can be difficult for new learners - for instance (as pertains to English speakers), the subjunctive mood in the Romance languages, or the complex systems for addressing subordinates or superiors in Japanese - learning a tonal language is not terribly difficult for most people whose native language is not tonal. Nevertheless, they seem to possess a certain mystique for many people. In this writeup I try to explain the basics of how tonal languages work.
What are tones?
All languages, whether or not they feature contrastive tones, use differences in tone to convey meaning. Think of the following exchange in English:
What are you doing?
What are you doing?
Imagine two people on a diet together, mutually pledged to help each other lose weight. One day, one of them sneaks off to the ice cream shop after work for a bowl of sweet, sweet Jamocha Almond Fudge - only to find her friend cheating on his diet at the very same time. The first person asks the second what he's doing - and the second one turns the question back on the interrogator. The emphasis on "doing" in the first sentence signals the asker's surprise at finding her friend cheating, and even manages to scold him for stopping at Baskin Robbins. The response emphasizes "you" - and nothing more than a shift in the pitch and rhythm of the sentence manages to communicate indignation at the hypocrisy of his friend for scolding him.
Say the two sentences aloud, and listen carefully to the sound of each one. The emphasized word is higher in pitch, louder, and longer in duration. The rhythm of the entire sentence changes as the emphasis moves. But consider how subtle the difference in sound is, compared to the significant difference in meaning between the two sentences. Even though English is not a tonal language, tone carries meaning in an English sentence, and so it's clear that the difference between a tonal language and a non-tonal one is not as profound as one might think.
The difference, then, is not that tonal languages are remarkable in using pitch to convey meaning, but that each word in a tonal language has a characteristic pitch. Because of that, it's possible to find pairs of words in a tonal language that sound identical except for the difference in their pitch. Such sets of words are called minimal pairs, and they're used to elucidate all sorts of features of languages' phonetic systems. For instance, in French, the words "beau" and "bon" /bo/ and /bõ/ differ only in that the latter has a nasal vowel; this minimal pair thus demonstrates that in French, nasalization is a meaningful contrast. In English, by comparison, nasal vowels predictably occur preceding nasal consonants, and thus a vowel's nasalization is not contrastive - that is, it doesn't communicate meaningful information.
Types of tones
Tonal languages have a specific set of tones (sometimes called tonemes, by analogy to phoneme and morpheme) and each syllable has one tone from that set. There are two basic types of tonal systems in languages. Register tones are simple pitches - most languages with register tone systems have only two or three - high and low, or high, middle, and low. Some languages, instead, have countour tones, in which each toneme has a specific shape. For example, Mandarin Chinese has four tones: high-level, rising, falling-rising, and falling. Because countour tones require less precise recognition and reproduction of pitches, languages with contour tones generally have more tonemes than those with register tones. Vietnamese, for instance, has six, and Cantonese has six or seven depending on dialect; many languages have more than that. I'm not aware of any register tone system as many tones.
Besides the languages properly categorized as tonal, there are languages with pitch accent, which lie somewhere between tonal and non-tonal. Well-known examples are Japanese, Swedish, and Norwegian, all of which are occasionally called 'tonal', although convention treats pitch accent as something separate from tone. English is an example of a language with stress accent - most words have a single stressed syllable (or a syllable with primary and another with secondary stress) that is longer, louder, and higher in pitch than other syllables. In languages with pitch accent, every syllable in a word has either a high or low pitch; the difference between pitch accent and a register tone system with only two tones is that in a register tone system, a word may have essentially any pattern of low and high tones in its syllables. Contrast that with Japanese, in which each word has an accented mora (morae being essentially the same as syllables) and a set of rules are used to determine what pitches the other morae carry.
In most pitch accent languages, some minimal pairs can be used to demonstrate that the pattern of pitches is salient and important to meaning; nevertheless, many fewer such pairs exist in pitch accent languages than in those with true contour tones - much like the location of the stressed syllable in English, which occasionally can distinguish pairs of words (present versus present, for instance) but not frequently. Besides the languages I've mentioned, it's widely agreed that Ancient Greek and Vedic Sanskrit (the Sanskrit spoken at the time that the Vedas, important Hindu holy texts, were written) had pitch accent. Because of this, it's considered likely that Proto-Indo-European had pitch accent.
Tone sandhi
Tone sandhi ("sandhi" is a Sanskrit word describing influence of sounds from one syllable on an adjacent syllable) is found in all tonal languages. If particular tones occur in adjacent syllables or words, the tone in one syllable will change to a different one. In standard Mandarin, there's only one tone sandhi rule. If there are two or more syllables in a row with the third (falling-rising) tone, all of those preceding the last change to the second (rising) tone. For example, the phrase "nǐ hǎo" (meaning "hello") is composed of two third-tone words in a row. When it's spoken, the first syllable changes to "ní", second tone, which makes the phrase easier to pronounce. While standard Mandarin only has one tone sandhi rule, other Chinese languages tend to have more complex tonal systems and correspondingly more complex sandhi rules.
Distribution
Many East Asian languages have tone. Much of the Sino-Tibetan language family, including all of the Chinese languages, are tonal. Vietnamese is tonal, though the rest of the Austroasiatic family is not. The Tai-Kadai languages, including Thai, are all tonal, as are the Miao-Yao languages (a group of languages spoken in southern China including Hmong). It is believed that these languages are tonal because of mutual influence, probably starting with either the Miao-Yao or Tai-Kadai languages. It's known that Ancient Chinese was not tonal, and it probably picked tones up from neighboring languages.
Of Africa's four main language families, the Nilo-Saharan and Khoisan languages are all tonal. Many languages in the Afro-Asiatic family are tonal as well, along with most Niger-Congo languages (including the very widely-spoken Yoruba), although the widespread languages Swahili and Wolof are not.
In the Americas, many Athabaskan languages (including Navajo) are tonal, but tones evolved twice, creating two different systems, in different branches of the family. Many other languages in North and South America are tonal as well. None of the Australian Aboriginal languages are tonal, but a few languages of New Guinea are.
Tone has been described by some as an areal feature, rather than a genetic one. This refers to the fact that many times, tone is found in neighboring languages in a region even if those languages don't share a 'genetic' affiliation - they don't belong to the same language family. It seems to be the case that long term language contact can result in languages borrowing tonal systems from one another.
Where do tones come from?
In most cases that are well-studied, tones seem to come about when consonant systems are simplified. It's known that the pitch of a vowel even in a non-tonal language tends to be very subtly affected by the neighboring consonants; if some change to a language's phonological system occurs, different tones can arise, replacing a distinction that used to be made with different consonants. Ancient Chinese, for instance, had a wider variety of consonants available than most modern dialects; it's theorized that as different sets of consonants merged or disappeared, tones arose to replace the distinction they created. This process is well known to have happened again in Chinese. Middle Chinese had a set of voiced initial consonants; most of the modern Chinese languages have no voiced syllable-initial consonants (except liquids). When the voiced initials /b, d, g/ merged with their voiceless equivalents /p, t, k/, the tone inventory of Middle Chinese (which originally had four tones) doubled, leading to eight tones at one stage in the language's evolution. Most of the modern Chinese dialects have simplified that tonal system, however.
Singing in tones
I'm not aware of much research into the question of how tones effect music, but a fascinating paper by Marjorie K.M. Chan explored the significance of tones in Cantonese pop music. She analyzed several songs, and looked at lines sung to the same melody with different lyrics. In each case, corresponding syllables had the same or similar tones (specifically, the tones ended on the same pitch.) It appears from her research that melodies match, to some extent, the contours of the tones. However, Mandarin pop music does not seem to respect tones at all - to the extent that recordings show that tone contours don't necessarily show up when in songs. However, in the traditional artform, Peking opera, a highly ritualized type of theater, singers do carefully reproduce tones.
Sources
My own knowledge and lots of linguistics classes, plus three years studying Mandarin Chinese
Chan, Marjorie K.M. Tone and Melody in Cantonese. http://people.cohums.ohio-state.edu/chan9/articles/bls13.htm
A very small portion of the section entitled "Distribution" came from Wikipedia. So sue me.