Here are John Finlay's remarks, from his 1808 publication HISTORICAL AND ROMANTIC BALLADS, CHIEFLY ANCIENT, from
http://www.archive.org/details/scottishhistori02finlgoog

THE GYPSIE LADDIE.

As Mr Ritson had mentioned, that neighbour-
ing tradition strongly vouched for the truth of
the story upon which this ballad is founded, I
resolved to make the necessary inquiries, the re-
sult of which, without much variation, is as
follows:

That the Earl of Cassilis had married a noble-
man's daughter contrary to her wishes, she ha-
ving been previously engaged to another; but
that the persuasion and importunity of her
friends at last brought her to consent: That Sir
John Faw of Dunbar, her former lover, seizing
the opportunity of the earl's absence on a fo-
reign embassy, disguised himself and a number
of his retainers as gypsies, and carried off the
lady, "nothing loth :" That the earl having re-
turned opportunely at the time of the commis-
sion of the act, and nowise inclined to partici-
pate in his consort's ideas on the subject, col-
lected his vassals, and pursued the lady and her
paramour to the borders of England, where,
having overtaken them, a battle ensued, in
which Faw and his followers were all killed or
taken prisoners, excepting one,
        ----the meanest of them all,
        Who lives to weep and sing their fall.
It is by this survivor that the ballad is supposed
to have been written. The earl, on bringing
back the fair fugitive, banished her a mensa et
thoro, and it is said confined her for life in a
tower at the village of Maybole, in Ayrshire,
built for the purpose; and, that nothing might
remain about this tower unappropriated to its
original destination, eight heads, carved in
stone, below one of the turrets, are said to be
the effigies of so many of the gypsies. The
lady herself, as well as the survivor of Faw's
followers, contributed to perpetuate the remem-
brance of the transaction; for if he wrote a
song about it, she wrought it in tapestry; and
this piece of workmanship is still preserved at
Culzean castle. It remains to be mentioned,
that the ford, by which the lady and her lover
crossed the river Doon from a wood near Cas-
sillis house, is still denominated the Gypsies
Steps.

There seems to be no reason for identifying
the hero with Johnie Faa, who was king of the
gypsies about the year 1590. The coincidence
of names, and the disguise assumed by the lo«
ver, is perhaps the foundation on which popu«
lar tradition has raised the structure. Upon
authority so vague, nothing can be assumed;
and indeed I am inclined to adopt the opinion
of a correspondent, that the whole story may
have been the invention of some feudal or po-
litical rival, to injure the character and hurt the
feelings of an opponent; at least, after a pretty
diligent search, I have been able to discover
nothing that in the slightest degree confirms
the popular tale.

Another source
http://www.maybole.org/history/books/legends/johnnyfaa.htm
concludes with:
"And therefore the most that can be said for the ballad now is that it is a fairly good specimen of the class of songs which delighted our ancestors. Historically, it is absolutely worthless, and worse, it is absolutely untrue."

I'm not trying to prove anything myself, I don't have a vested interest in the story being true or untrue. So, a strong local tradition in 1808, but no corroboration; the tune consistently linked with the lyric by having Johnie Faa or Lady Cassilis as its title goes back to 'c.1620'; the earliest dated lyric is 1737.

But I've seen the Maybole heads myself (I don't know if anyone has seen the tapestry so often mentioned) and was told they were the gypsies' heads - is it all made up, including the heads?