"anything that guides or directs in an intricate case," 1590s, a special use of a revised spelling of clew "a ball of thread or yarn" (q.v.). The word, which is native Germanic, in Middle English was clewe, also cleue; some words borrowed from Old French in -ue, -eu also were spelled -ew in Middle English, such as blew, imbew, but these later were reformed to -ue, and this process was extended to native words (hue, true, clue) which had ended in a vowel and -w. The spelling clue is first attested mid-15c.
The sense shift is originally in reference to the clew of thread given by Ariadne to Theseus to use as a guide out of the Labyrinth in Greek mythology. The purely figurative sense of "that which points the way," without regard to labyrinths, is from 1620s. As something which a bewildered person does not have, by 1948.
Thus hardy Theseus, with intrepid Feet,
Travers'd the dang'rous Labyrinth of Crete;
But still the wandring Passes forc'd his Stay,
Till Ariadne's Clue unwinds the Way
[Gay, "Trivia"]
The board game (originally Cluedo) was launched in 1949 in Britain.