I have upvoted
Pike's write-up above as a good succinct explanation of a click, so don't think I am slighting of it by offering a fuller explanation. Clicks are certainly the hardest and most complicated sounds in any language. Deep breath...
In phonetics, an ingressive and velaric sound. That is, it is made by closing the mouth at some point, and making an additional contact of the back of the tongue against the soft palate (the velum). The tongue is then pulled back to deform the mouth cavity and rarefy the air within it. When the outer stoppage is released, air rushes into the mouth where the pressure is lower. That's the theory.
The sounds so produced include the disapproving tut-tut or tsk-tsk noise used in English. The only languages that use these as speech sounds, however, are found in southern Africa in the Khoisan languages of the "Bushmen" and "Hottentots", and in neighbouring Bantu languages like Zulu and Xhosa that must have borrowed them fairly recently; and also two languages called Sandawe and Hadza in Tanzania that appear to be distantly related to Khoisan. Recently I read that an unrelated Cushitic language in Kenya, called Dahalo, also has clicks: this is new to me and is not mentioned in older sources. It seems the Dahalo people were originally Khoisan speakers who later adopted Cushitic from their neighbours but retained some of their old words.
Update, 18 March 2003. For latest scientific theory on the deep relationship between click languages and relevance to human evolution, see my postscript under Khoisan.
In Zulu and Xhosa the alveolar click is written as C, the lateral one as X, and the retroflex on as Q. Each of these can also be voiced (written e.g. GQ), nasalized (written e.g. NQ), or aspirated (written e.g. QH). I can't make any of those variations.
In the Khoisan languages they have traditionally been written with a variety of punctuation marks, e.g. the exclamation mark in !Kung and !Xam. The International Phonetic Alphabet (IPA) used to have a number of its own special characters for them, but recently adopted the traditional punctuation signs instead. This is how the IPA describe them:
A bilabial click is a circle with a dot in it.
A dental click is a vertical line (pipe).
A (post)alveolar click is an exclamation mark.
A palatoalveolar click is a kind of not-equals sign, or a pipe with two crossbars.
An alveolar lateral click is two pipes.
In traditional use, the pipe is often written as a slash.
And no I don't know what, if the above is true, the difference between !K and !X is, because I frankly admit I'm now way out of my depth and if I try to pursue it I'll start singing in falsetto and plucking daisies out of my hair.
Remarkably, clicks also occurred outside Africa, in a ceremonial form of one of the Australian Aboriginal languages called Lardil. The ceremonial form Damin, now no longer fluently spoken by any surviving tribe members, was much simplified in grammatical and vocabulary aspects, but had an extremely unusual phonology: see http://www.invisiblelighthouse.com/langlab/damin.html