From a citation (#4) under the article about the song in Wiki:

See Othello, 4:3, in which Desdemona sings a willow song and asks Emilia about omens of weeping. Another Elizabethan willow song mentions the wearing of the green willow; this is in a poem by John Heywood, dated circa 1545 (Br. Mus. addit. No. 15,233): "All a green willow, willow, willow, All a green willow is my garland." See Norman Ault, Elizabethan Lyrics, pp. 14–15, 519 (1949). Robert George Whitney Bolwell, The Life and Works of John Heywood, identifies this Heywood work as the song "The Ballad of the Green Willow". He points out that this is a predecessor of Shakespeare's Willow Song, which merely changes the word "is" in the refrain to "must be".

So there is something traditional in the willow representing sadness at the loss and yearning for the return of a loved one. I can't for the life of me remember where, but I read a few years ago that Steeleye's version (which I love) stands out because it's upbeat, in spite of the theme.

I have a recording somewhere of Kathleen Ferrier singing a version of the Elizabethan song mentioned in the citation. And I couldn't help help thinking of "Tie a Yellow Ribbon" as having a sort of parallel sentiment...