To be caught in the act of committing a misdemeanour, with the evidence there for all to see.
The Red Hand has long been a heraldic and cultural symbol of the northern Irish province of Ulster. One of the many myths as to its origin is the tale of how, in a boat race in which the first to touch the shore of Ulster was to become the province's ruler, one contestant guaranteed his win by cutting off his hand and throwing it to the shore ahead of his rivals. The potency of the symbol remains and is used in the Ulster flag, and as recently as the 1970s a group of Ulster loyalist paramilitaries named themselves the Red Hand Commandos.
Red-handed doesn't have a mythical origin however - it is a straightforward allusion to having blood on one's hands after the execution of a murder or a poaching session. The term originates, not from Northern Ireland, but from a country not so far from there, socially and geographically, i.e. Scotland. An earlier form of 'red-handed', simply 'red hand', dates back to a usage in the Scottish Acts of Parliament of James I, 1432.
Red-hand appears in print many times in Scottish legal proceedings from the 15th century onward; for example, this piece from Sir George Mackenzie's A discourse upon the laws and customs of Scotland in matters criminal, 1674:
"If he be not taken red-hand the sheriff cannot proceed against him."
The earliest known printed version of 'red-handed' is from Sir Walter Scott's Ivanhoe, 1819:
"I did but tie one fellow, who was taken redhanded and in the fact, to the horns of a wild stag."
Scott was an avid student of Scottish history and folklore, which he relentlessly mined for inspiration in his novel writing. He is certain to have heard 'redhand' before writing Ivanhoe. The step from 'redhand' to 'redhanded' isn't large, so calling Scott the originator of the term is perhaps being over generous to him. Nevertheless, the enormous popularity of his books certainly brought 'red-handed' to a wide audience and, without him, the term might now be long forgotten.
16th and 17th century Scottish sources provide various examples of 'apprehended redhand', 'taken with redhand' etc. but the earliest known citation of the currently used 'caught red-handed' phrase is in the English novelist George Alfred Lawrence's work Guy Livingstone; or, 'Thorough', 1857:
My companion picked up the object; and we had just time to make out that it was a bell-handle and name-plate, when the pursuers came up - six or seven "peelers" and specials, with a ruck of men and boys. We were collared on the instant. The fact of the property being found in our possession constituted a 'flagrans delictum' - we were caught "red-handed."
See also - phrases coined by Sir Walter Scott.