From the rec.martial-arts FAQ:
The belt system, as a formalized method of indicating rank, was popularized by Professor Jigaro Kano, founder of Kodokan Judo, around the beginning of this [the 20th] century. There are varying opinions as to whether the practice predated Kano's use of it, and where it may have come from, but it certainly wasn't common (the more traditional practice in Japanese martial arts was, and is, the granting of scrolls indicating various levels of abilities). The practice was adopted by Karate, formerly a fairly obscure Okinawan folk art, as that art was brought into the mainstream of Japanese martial arts. Many arts have since adopted it -- for example, some Western schools teaching Chinese martial arts use it, though this practice is somewhere between uncommon and unheard of in China itself. Some of these schemes are elaborately hierarchial; some schools use no belt ranking system at all. White belts almost always indicate beginners, black belts indicate those who have reached some level of ability. There are various colors used for rankings both below black belt, and for high ranking black belts, and various explanations as to what they mean. The color scheme -- and the implications for school etiquette -- vary from system to system and perhaps from school to school. An often heard story holds that the colours are explained as follows: a trainee's belts, which, traditionally, were never washed, became progressively dirtier with time (starting out white, becoming yellow with sweat, green with grass stains, and so on), finally changing to black over the years. This explanation, alas, is almost certainly fanciful. The best source of information on the meanings of belt colors and the proper behavior with respect to rank is, as always, one's teacher.Long time Shotokan instructor Steve Gombosi chimes in:
"in the traditional days before Kano invented Judo", there *was* no kyu/dan ranking system. Kano invented it when he awarded "shodan" to two of his senior students (Saito and Tomita) in 1883. Even then, there was no external differentiation between yudansha (dan ranks) and mudansha (those who hadn't yet attained dan ranking). Kano apparently began the custom of having his yudansha wear black obis in 1886. These obis weren't the belts karateka and judoka wear today - Kano hadn't invented the judogi yet, and his students were still practicing in kimono. They were the wide obi still worn with formal kimono. In 1907, Kano introduced the modern gi and its modern obi, but he still only used white and black.
Karateka in Okinawa didn't use any sort of special uniform at all in the old days. The kyu/dan ranking system, and the modern karategi (modified judogi) were first adopted by Funakoshi in an effort to encourage karate's acceptance by the Japanese. He awarded the first "shodan" ranks given in karate to Tokuda, Otsuka, Akiba, Shimizu, Hirose, Gima, and Kasuya on April 10, 1924. The adoption of the kyu/dan system and the adoption of a standard uniform based on the judogi were 2 of the 4 conditions which the Dai-Nippon Butokukai required before recognizing karate as a "real" martial art. If you look at photographs of Okinawan karateka training in the early part of this century, you'll see that they were training in their everyday clothes, or (!) in their underwear.