With regard to the origin of the saying that various posters on this page have attributed to Shakespeare, I note that it appears in John Heywood, A dialogue conteinyng the nomber in effect of all the prouerbes in the englishe tongue compacte in a matter concernyng two maner of mariages (1546) in the following form:
All is not golde that glistreth by olde tolde tales.
So Heywood reports in 1546 that the expression is an "olde told tale"—that is, a proverb. Shakespeare was born in 1564.
Likewise, in John Proctor, The Fal of the Late Arrian (1549):
But Christen Reader, thou hast learned by datlye experience, that all is not golde, which glystereth : And euery tree which doth floure and blossome fayre to the eye, yeldeth not the best fruyte in thende.
Earlier than these is the following instance in a 1534 translation of Joachim Vadianus, A worke entytled of ye olde god [and] the newe of the olde faythe [and] the newe, of the olde doctryne and ye newe, or orygynall begynnynge of idolatrye:
There is a comen prouerbe whiche goeth aboute / and it is full true. Not all that glytterethe is golde : what comparisō is there betwen chaffe
and pure fyne whete? As who shold say, none at al.
Vadianus was Swiss, but it is unclear whether he is quoting a Swiss version of the proverb here or whether his English translator is interposing an English proverb to capture the tenor of Vadianus's original text.
But earlier still is this instance from Thomas Usk, The Testament of Love (printed in 1542 but written in 1388):
Anone as fylled is your luste, manye of you be so trewe, that lytell hede take ye of suche kyndenesse, but wyth traysoun anon ye thynke hem begyle, and let lyght of that thynge whyche fyrste ye maked to you wonders dere, so what thyng to women it is to loue any wight er she hym well knowe, & haue him proued in many halfe, for euery glyttryng thynge is nat golde, & vnder colour of fayre speche many vices may be hid and conseled.
The publisher of the 1542 edition of The Testament of Love thought that it had been written by Chaucer, but subsequent scholarship has assigned it to Usk, an interesting character, to judge from his Wikipedia page.