I am an idiot, I forgot to look in the obvious place. Perseus also has Sir Thomas North's translation of Plutarch's life of Theseus (this is the translation Shakespeare used for his plays "Julius Caesar" and "Anthony and Cleopatra"). The relevant part says in English:

Furthermore, after he was arrived in Creta, he slew there the Minotaur (as the most part of ancient authors do write) by the means and help of Ariadne: who being fallen in fancy with him, did give him a clue of thread, by the help whereof she taught him, how he might easily wind out of the turnings and crancks of the labyrinth.

(http://perseus.csad.ox.ac.uk/cgi-bin/ptext?doc=Perseus:text:1999.03.0078&query=chapter=#281&layout=&loc=Thes. 18)

Plutarch also uses the Greek word linon I mentioned in my previous post. However, I have this idea that Sir Thomas North did not translate direct from the Greek, but translated a French (?) translation of Plutarch into English.

Also relevant is Chaucer's Legend of Good Women (I had a vague feeling Chaucer wrote about Theseus and found this by googling Chaucer Theseus Ariadne, where I found a reference to the Legend of Good Women amongst all the stuff about the Knight's Tale, which is about a different episode in Theseus's life, and then googling Chaucer Legend of Good Women). Lines 2012 to 2018 read:

And, for the hous is crinkled to and fro,
And hath so queinte weyes for to go --
For hit is shapen as the mase is wroght --
(130) Therto have I a remedie in my thoght,
That, by a clewe of twyne, as he hath goon,
The same wey he may returne anoon,
Folwing alwey the threed, as he hath come.


I'll leave it to someone else to find something on Chaucer's sources for this or to push it further back.