Unlike the other two primary colors we've discussed so far, kachol כחול (blue) does not appear in the Torah at all. In fact, the only appearance of any form of the root כחל is in Yechezkel 23:40: כָּחַלְתְּ עֵינַיִךְ - "you painted your eyes." The verb כחל meant exactly that - painting of the eyes (eyelids). We find it mentioned for cosmetic purposes (this is the source of the expression בלא כחל ובלא שרק - meaning "without additions". It literally means "without any makeup" and in Ketubot 17a, was used as praise for the bride - she would be beautiful even without any makeup.) The word מכחול - painters brush, has its origins here. The word kohl still has the meaning of "a cosmetic preparation, such as powdered antimony sulfide, used especially in the Middle East to darken the rims of the eyelids."
It was also used for medicinal purposes for the eyes, as found in Shabbat 78a. Stahl writes that the Arabic word for optometrist - כחאל - derives from this sense of the word.
Most of the sources I have read simply (Klein, for example) say that the color used in the eye makeup was blue, and from here we derive the name of the color kachol. I'm not fully convinced of this. While I can't really use Jastrow as a full concordance of the Talmudic literature, in none of his examples does he identify kachol - or any of its cognates - with "blue". He does, however, give a few examples where it actually refers to another color. For example, he identifies the stone כוחלין as carbuncle, which is red (see more about that here.) He also says that the origin of the Hebrew word for a cow's udder - כחל - is due to its reddish color. (Steinberg also says that the root כחל is related to חכל - which everyone agrees means "red"**.)
Jastrow also identifies the stone כוחלא (Kiddushin 12a, Bava Batra 4a) as being black. Perhaps he is being a bit biased here. In Bava Batra, while Rabbeinu Gershon does define כוחלא as black, Rashi suggests kachol - which clearly meant to him "blue". But even if Jastrow for some reason is choosing to deliberately ignore the possibility that כחל could mean blue, there are still a lot of open questions. My guess? I think probably כחל originally only meant "to paint", and later - at least by Rashi's time - kachol fully meant blue.
One interesting etymology that comes out of this word is that of the English word alcohol. Klein writes:
Arab. alkohl, vulgar pronunciation of alkuhl, from al (= the) and kohl, resp. kuhl (= antimony used for painting the eyelids), which is related to Hebrew כחל (= he painted the eyes with antimony). Its modern sense ('highly rectified spirits') is due to the analogy of the fitness of this powder.
Others say that the process of producing the makeup was similar to that of producing alcohol - hence the name.
According to Rosenthal, in Modern Israeli slang, k'cholim refers either to police officers or soldiers in the Air Force - both based on the blue color of their uniforms.
** After publishing this post, I have found a notable source that disagrees. The Ramban on Bereshit 49:12 says that חכלילי means kachol, not red. However, it does not seem that he meant "blue" but rather "dark". For more information, see the Daat Mikra on the verse, and this article by Prof. Aaron Demsky: here in English, and here in Hebrew. There is an interesting archeological discovery with a First Temple jar saying "wine kachol". (A picture can be found in the Daat Mikra).