"That which points the way, indicates a solution, or puts one on the track of a discovery; a key."
-- The OED
The word clue has a wonderfully tangled history. First off, clue is a horrible, inexplicable corruption of the obviously superior original spelling, 'clew'. This elder spelling is still used today to refer to a ball of yarn or thread. The newer spelling, by pure chance, has become associated with the newer meaning, as defined above, which is actually a figurative usage that took centuries to become commonplace.
"Therto have I a remedie in my thoght,
By a clewe of twyn as he hath gon,
The same weye he may returne a-non,
ffolwynge alwey the thred as he hath come."
The Legend of Ariadne, Part VI of The Legend of Good Women, by Geoffrey Chaucer, 1387
"Having lost the Clue which led us in, We wandered in the Labyrinth of Lust."
The Legend of Piers Gaveston by Michael Drayton, 1593
In this sense 'clue' was used as a familiar metaphor; a reference to the myth of Theseus. Theseus, the prince of Athens, volunteered to fight the monstrous Minotaur; however, fighting the Minotaur was only half the battle, as it lived in a vast labyrinth. In order to find his way out, Theseus unrolled a ball of thread behind him, and was thus able to retrace his steps and escape the labyrinth.
"Seeking in the movements of the heavenly bodies for a clue to the accidents of life and the revolutions of nations."
Journal of a Voyage Into the Mediterranean by By Sir Kenelm Digby, 1628
By the mid 1600s this metaphor had become so familiar that one no longer needed to mention the labyrinth to make the context clear. This is an important landmark, because before this one might be easily confused between Theseus' clue, which led one through a puzzle, and the clue of The Fates, spun and cut to determine the length of mortal lives. (as in "The old man knowes how little of his clew is left in the winding" -- The Balm of Gilead by Joseph Hall, 1650).
I cannot begin to locate the point when a clue stopped being a thread and devolved into a single object or event. It appears that it was in the late 1800s that people regularly stopped referring to 'the clue' of a puzzle, and started referring to 'a clue'. But as evidenced by the Digby quote above, this was not entirely new. This change is a bit sad, as both poetically and narratively, referring to a clue as a guide threaded through a mystery is much more satisfying.