It's always a good idea to give references in cases like this, as so much imaginary nonsense is presented as (unproven) "fact" by people (present company excepted) who have heard or seem to remember reading all manner of unlikely things; that way, you're less likely to get the blame when it all turns out to be fiction!
Iona and Peter Opie (The Oxford Book of Nursery Rhymes, 1951) had this to say:
"It is possible (as has been frequently stated) that this rhyme has a religious background; that it is a word-picture of Our Lady's convent has been suggested, the bells being the sanctus bells, the cockleshells the badges of the pilgrims, the pretty maids the nuns rank behind rank at offìce. But there is disagreement as to the significance of the piece as a whole. Catholic writers feel it to be a lament for the persecution of the Roman Church; Protestant writers declare it is a lament at the reinstatement of the Roman Church. Popular tradition has it that the original Mary was Mary Queen of Scots, who with her gay, French, and Popish inclinations much displeased the dour John Knox. In this case the pretty maids might be the renowned Four Marys, her ladies-in-waiting, and it has even been stated that the cockleshells were the decorations upon a particular dress she was given by the Dauphin. Such assertions are, of course, the work of the "happy guessers". No proof has been found that the rhyme was known before the eighteenth century. It is to be remarked, however, that there is a tune Cuckolds all a row in the I651 edition of Playford's Dancing Master. The last line of the 1780 version of the rhyme goes Sing cuckolds all on a row and it could well be sung to the tune in The Dancing Master."
The first reference they give is toTom Thumb's Pretty Song Book (M. Cooper), vol. ii, c.1744.
Mistress Mary Quite contrary,
How does your Garden grow?
With Silver Bells, And Cockle Shells,
And so my Garden grows.
For what it's worth, there is a text of Cuckolds, from D'Urfey's Pills to Purge Melancholy (1719-20), with tune, in the DT: