The version I heard was that Henry VIII wrote the words for Ann Boleyn and set them to a traditional tune. As for "Greensleeves," sleeves were separate from bodices and jerkins at that time, and a pair of sleeves were often a fancy gift.

From the SCA website:

Alas, my love, you've done me dirt,
For you've sewn green sleeves to my purple shirt.
And then you've done me worse than that--
You've made me go out and wear it.