A kufi is a type of headcovering, typically worn by Muslim males. It's similiar to a kipa/yarmukle, which is what Jewish men wear, although a kufi is larger, covering alll the hair. It is also known as a "prayer cap", and a "skullcap." In the Arab world it is sometimes known as a keffiyeh, and in South Asia, it's often known as a "topi."

According to Islam, Muslim men aren't required to cover their hair in everyday life, but doing so is recommended and brings reward to those who do so. It was the practice of the Prophet Muhammad (pbuh) and his companions to cover their heads with kufis, turbans, etc. It is a reccomended, but not obligatory thing to do. For males, it is also considered mustahab ("prasieworthy" or "seeking the love of God") to cover one's head during prayer.

A hadith mentioned in the books Abu Dawood and Tirmidhi quotes Muhammad (pbuh) as saying "The distinction between us and the polytheists is the turbans over our caps." As a result, if a Muslim wears a turban, he puts a cap on underneath to differentiate himself from others, such as sikhs or Jewish and Christian Arabs (who wore turbans as well).

What does a Kufi look like? There are various styles, and they vary. Some look like a simple white cap with no brim, others look boxy, and others look like a basic hairnet. Some are plain woven cotton, and others are embroidered. They are always round (at least, in my experience).

Kufis are popular in many Muslim countries. A lot of people think that a Kufi is only specific to Africa, as they seem to have the most colorful Kufis, along with the fact that most Muslims in the US are African-American, so people sometimes mistake a Kufi for being a cultural symbol (like Kwanzaa I guess), rather than a religious one. There is also a mistaken belief by a few that all Muslims wear turbans. Kufis are quite popular among Muslims, if you see images of people in Afghanistan, Bangladesh, Indonesia, Malaysia, Pakistan, parts of India, etc., you will likely see people wearing kufis on the streets.

Examples of Kufis:
http://www.shukronline.com/mens-hats.html (Muslim kufis)
http://www.wilsdom.com/store/page32.html (African kufis)

A list of hadith and excerpts from Fatwas concerning wearing Kufis: http://www.zawaj.com/articles/sunna_clothes.html