"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
The board game (originally Cluedo) was launched in 1949 in Britain.
"to indicate by means of a clue," 1934; "to inform someone of the important facts," usually with in, 1948, from clue (n.). Related: Clued; cluing. Earlier in now-obsolete sense of "follow or track by clues" (1660s). In nautical use, "to haul up (a sail) by means of the clue-lines," from clue (n.) in the "wound ball of yarn" sense.