Taken from Phrases.org.uk
To apply unnecessary ornament - to over embellish.
From Shakespeare's King John, 1595:
Therefore, to be possess'd with double pomp,
To guard a title that was rich before,
To gild refined gold, to paint the lily,
To throw a perfume on the violet,
To smooth the ice, or add another hue
Unto the rainbow, or with taper-light
To seek the beauteous eye of heaven to garnish,
Is wasteful and ridiculous excess.
The context of that speech in the play is King John's satisfaction with his second coronation - "Here once again we sit, once again crown'd". His courtiers aren't so sure, calling the crowning 'superfluous'. The use of Shakespeare's text to denote unnecessary ornamentation is fairly straightforward. After all, 'to gild' is to cover with a thin layer of gold, so 'gilding refined gold' is obviously unnecessary. Unfortunately, remembering text from Shakespeare isn't everyone's forte and the quotation has become rather garbled. As the quotation above shows, 'gild the lily' doesn't appear in the original.
The term 'paint the lily' was used in the 20th century, with the same meaning we now apply to 'gild the lily'. Clearly, this is the correct quotation. The two versions coexisted for a time, although 'paint the lily' is now hardly ever used. The first citation I can find for 'gild the lily' comes from the USA, in the Newark Daily Advocate, 1895, in what appears to be a half-remembered version of Shakespeare:
One may gild the lily and paint the rose, but to convey by words only an adequate idea of the hats and bonnets now exhibited absolutely passes human ability.