Dunno when it was first recorded, but Pepys did mention having heard the song in Scotland. I first heard it sung in a folk venue by Nic Jones; the version beginning "In scarlet town". The version sung in Scotland opens with either "'Twas round about the Mart'nmas time" or "Round about the Lammas tide".