From the Facts on File Encyclopedia of Word and Phrase Origins, by Robert Hendrickson:

“Since there are no nuts to be gathered in May, the old children’s song with the words, ‘Here we go gathering nuts in May’ seems to make no sense – and indeed, it may have been intended as a nonsense song. But ‘the nuts’ in the phrase has been explained as being ‘knots’ of May, that is, bunches of flowers. In Elizabethan England, Queen Elizabeth herself gathered knots of May in the meadows, one author tells us, and this is a plausible explanation even though there are no recorded quotations supporting the use of knots for ‘flowers,’ except possibly the English knot garden of herbs.”