A shemagh is an Arabian head scarf which completely covers the head and most of the face, leaving only the eyes exposed. It is a simple and effective garment, protecting the wearer from the sun and from blowing dust and sand.
These are closely related to the keffiyeh, familiar to Westerners as the traditional headgear of Palestinian politicians (including Yasser Arafat), but a shemagh also wraps under to cover the nose and mouth, and are likely most familiar to Americans as being worn by various camel riding warriors from any number of films. The shemagh may be worn with or without an agal, the cord that goes around the crown of the head to secure the scarf.
A shemagh is actually nothing more than a square of cloth about 2-3 ft. (0.5 - 1.0 m) square, usually patterned in black and white, although many colors are available. It is folded into a triangle and wrapped around the head, starting at one shoulder, going over the forehead, down and across the nose and mouth, and around the back of the head. The two corners are then tied together over the temple on the same side as the shoulder at which you started. I can't really describe this very well, so here's a site that has photos.
Shemagh are traditionally worn by men, not women. A shemagh does not equal a hijab. Nonetheless, they are now sold as a female garment in Western countries. This is probably a good thing, but you probably shouldn't wear them when vacationing in the Middle East unless you have checked on local mores with a trustworthy source.
Thanks to XWiz for help with the tying of the shemagh.