According Evan Morris (a.k.a. The Word Detective), the term originated in 15th century England, referring to the blood-stained hands of an individual who hadn't yet found the time to wash clean the evidence of his crime. Interestingly enough, no specific crime is associated with the origin of this word, as it seemed appropriate to describe several common misdeeds, such as homicide, killing livestock or even theft from a butchery.

The term came into common use in the 1700's, and found its way into the Oxford English Dictionary in the 1800's.

Many thanks to The Word Detective, via http://word-detective.com