The song is #39 in Iona & Peter Opie's The Oxford Dictionary of Nursery Rhymes (pp 82-84):

39

Bessy Bell and Mary Gray,
They were two bonny lasses;
They built their house upon the lea,
And covered it with rushes.

Bessy kept the garden gate,
And Mary kept the pantry;
Bessy always had to wait,
While Mary lived in plenty.


This is an adaptation of a pathetic little Scottish ballad:

O Bessie Bell and Mary Gray,
They war twa bonnie lasses;
They bigget a bower on yon burn-brae
And theekit it o'er wi' rashes.

They theekit it o'er wi' rashes green,
They theekit it o'er wi' heather;
But the pest cam' frae the burrows-town,
And slew them baith thegither.

They thocht to lye in Methven kirk-yard,
Amang their noble kin;
But they maun lie on Lynedoch-brae,
To biek forenent the sin.

The local tradition (first written down c. 1773) about these two girls is that Mary Gray was the daughter of the Laird of Lednock (also known as Lyne-doch) and Bessy Bell of the Laird of Kinvaid, a place near by. They were both very handsome and an intimate friendship subsisted between them. While Bessy was on a visit to Mary the plague broke out at Perth (seven miles distant), and in order to escape it they built themselves a bower about three-quarters of a mile west from Lednock House, in a retired and romantic place called Burn-braes. Here they lived for some time; but, the plague raging with great fury, they caught the infection from a young man who was in love with them both and used to bring them their provisions. They died in this bower, and since, according to the rule in cases of plague, they could not be buried in a churchyard (verse 3), they were interred in the Dranoch-haugh, at the foot of a brae of the same name, near the bank of the river Almond. The burial place (which may still be seen) lies about three-quarters of a mile west from the house called Lynedoch Cottage. The date of this episode would be about 1645. In that year, and the year or two following, Perth and its neighbourhood was ravaged by plague; 3,000 people are believed to have perished. In spite of the tenor of the ballad it is likely that the girls had already caught the infection when they removed to their bower. It is written in an account of the plague, made soon afterwards, that 'it was thought proper to put those out of the town at some distance who were sick. Accordingly, they went out and builded huts for themselves in different places around the town, particularly in... the grounds near the River Almond.' The ballad was known in the late seventeenth century since there was a squib on the birth of the Old Pretender (1688), beginning:

Bessy Bell and Mary Grey,
Those famous bonny lasses.

The ballad was later (1719) converted into a drawing-room song by Allan Ramsay, who, nevertheless, retained the first verse.
Ramsay's version, first printed in a pamphlet (Edinburgh, 1720), appears frequently in the 18th century, e.g. Orpheus Caledonius, 1725, 'set to music by W. Thomson'; The Musical Miscellany (John Watts), 1729; O Bessy Bell & Mary Gray, c. T730, 'A Scotch song, Sung by Mrs. Robinson at the King's Theatre in the Haymarket'; Muses Threnodie, James Cart, 1774; The Pirate, Walter Scott, 1821 (two verses). The tune is also in The Beggar's Opera, 'A curse attends the woman's love'. The ballad is given in A Ballad Book, C. Kirkpatrick Sharpe, 1824; The Songs of Scotland, A. Cunningham, 1825, as recited by Sir Walter Scott; Ancient Ballads and Songs, Thomas Lyle, 1827, two verses. As a nursery rhyme it appears in The Cheerful Warbler (J. Kendrew), c. 1820, first verse only, 'They built their house with walls of clay'; JOH, 1842; Rymour Club, 1911.

*** ‘Bessy Bell’ is possibly a traditional name. Martin Parker wrote a ballad ‘Four-pence-halfe-penney Farthing' registered 9 Nov. 1629, which was to the tune 'Bessy Bell; or, A Health to Betty', and there is a poem on 'Bessy Bell' attached to Barnabee’s Journal. Ritson wrote as if there were already more than one song about ‘Bessy Bell and Mary Gray' in 1795.

And here's the Steeleye Span version of the song:

https://www.youtube.com/watch?v=WPjqQ_61CkM