This expression has its origins in Scotland. Given the context it was often used in the earliest references, the phrase 'red hand' or 'redhand' probably came about referring to people caught with blood on their hands. The first known documented instance of “red hand” is in the Scottish Acts of Parliament of James I, written in 1432: "That the offender be taken reid hand, may be persewed, and put to the knawledge of ane Assise, befoir the Barron or Landeslord of the land or ground, quhidder the offender be his tennent, unto quhom the wrang is done or not… And uthers not taken reid hand, to be alwaies persewed…"
The first documented instance of the expression morphing from 'red
hand' to 'red handed' was in the early 19th century work Ivanhoe,
written by Sir Walter Scott: "I did but tie one fellow, who was
taken redhanded and in the fact, to the horns of a wild stag."
It later showed up in 'Guy Livingstone' written by George Alfred
Lawrence and published in 1857: "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."