The keffiyeh (and many other transliterations from the Arabic, such as "gahfiyya") is the name of the knitted/crocheted, usually white, cotton
skullcap worn underneath an
Arabian man's
ghutra to provide a "foundation" for the large headcloth, holding it in place. They can be embroidered.
Many Western sources refer to the headcloth itself as a keffiyeh, but they haven't got the terminology straight; all the Middle Eastern sources I can find say that the keffiyeh is the underlayer and the large cloth is the ghutra.
Sources:
http://www.kuwait-info.org/Country_Profile/Society_and_Culture/
Society/Men_s_Dress/men_s_dress.html
http://www.florilegium.org/files/ACCESS/turbans-msg.html
http://www.ecssr.ac.ae/Land/costum.html
http://www.saudinf.com/main/q031.htm