A modern detective looks for clues. The Old English word from which "clue" descends had a much more concrete meaning: cliwen, later clew, was a "ball of thread or yarn." The metaphor was made by classical literature; the spelling change is purely English.
Theseus and the Thread
In Greek mythology, the Athenian hero Theseus was sent into the labyrinth at Knossos to face the Minotaur. Princess Ariadne, who had fallen in love with him, gave him a ball of thread. He tied one end to the entrance and unwound the ball as he walked, so that after killing the monster he could find his way back out. Without the thread, the labyrinth would have been a death trap.
Renaissance and early modern English writers, retelling this story, used the word clew for that life-saving ball. By extension, "to follow a clew" came to mean "to follow a guiding thread through any tangled situation." From there it was a short metaphorical step to the modern sense: a piece of evidence that helps you find your way to the solution of a mystery.
A Spelling Change in the 17th Century
The older spelling clew persisted into the 17th century, especially in nautical contexts (a clew is still a corner of a sail in seamanship today). The "clue" spelling, with the modern figurative sense of "hint" or "evidence," took over during the 1600s. Detective fiction, beginning in the 19th century, made the new sense the dominant one. By the time of Sherlock Holmes, "clue" had almost entirely lost its association with thread.
A Family of Tangled Words
The metaphor of a guiding thread is buried in several other English expressions: to unravel a mystery, to find a thread of an argument, a tangled situation. All of them owe something, knowingly or not, to Ariadne's gift to Theseus.