By an amazing bit of synchronicity, a book I bought in a second-hand shop in Rochester, because it had the Cutty Wren in it, because I had seen the reference to it here, because I wanted the words for Red Nose Day, also has background on this song. (Stories of Britain in Song, Forbes Stuart, Longman Young, 1972)

It gives John Knox as a source: "In the very time of the General Assembly, there comes to public knowledge a haynous murther, committed in the court; yea, not far from the Queen's lap; for a French woman, that served in the Queen's Chamber, had played the whore with the Queen's own apothecary. the woman conceived and bare a child, whom, with common consent, the father and mother murthered; yet were the cries of a new-borne childe hearde, searche was made, the child and the mother were both apprehended, and so were the man and the woman condemned to be hanged in the publicke street of Edinburgh. the punishment was suitable, because the crime was haynous.

But yet was not the court purged of whores and whoredoms, which was the fountaine of such enormities; for it was well-known that lust hasted marriage betwixt John Sempill, called the Dancer, and Mary Livingstone, surnamed the Lusty. What bruit the Maries, and the rest of the dancers of the court had, the ballads of that age doe witnesse, which we for modestie's sake omit."

It also states that Sir Walter Scott found evidence of the same story in both the court of Peter the Great and in France, with the French woman becoming Mary Hamilton, the man Henry Darnley, and the time when Mary, as Queen Dowager of France, had not returned home.