The song and the various derivations are based on Scottish Gypsy history. Johnnie Faa was the first of the gypsy royals in the Borders area of Scotland (Yetholm). This was an official title granted to him by the King of Scotland for services rendered (he is referred to in records as "most belovit of the King); they were staunch supporters of the Scottish crown against the English and were hung as criminals or transported in prison ships for being so. The character Meg Merilees by Walter Scott is based on the Wife of Johnnie Faa's grandson. Her name was Jean Gordon and she ended up being drowned for being a jacobite.
People seem to be hung up on the line he is no gypsy ... but lord of these lands all over. Well the thing is, he was both: he was a gypsy but also lord of these lands.