Stan Hugill expressed surprise that this song was not mentioned in earlier shanty collections, and he seems to have picked it up during his own sailing days. He claims that the heroine originally bore the name Nelly Ray, and the first written mention of the song was in a diary belonging to Charles Picknell, a sailor aboard the convict ship Kains, which departed from London to Van Diemen's Land (Tasmania) on July 8, 1830.
A careful recording of the history of the Kains can be found on the Free Settler or Felon website. Some of Picknell's diary entries are preserved in the 1930 Sydney Morning Herald: May 10, May 17, and May 24. Meanwhile, the journal was published in the London periodical Blue Peter. The song appeared at the end of the journal, which has since been reprinted as The Kains: Female Convict Vessel (Adelaide: Sullivan's Cove, 1989). Mudcatter "Lighter" and others give a breakdown of the lyrical anachronisms here. Richard Edmunds suggests the song is an 1870s musichouse parody of "Darling Nelly Gray" in the most careful writeup of the history of the song. The Welsh baritone J. W. Myers first recorded the song in October, 1905. The Beatles recorded a fragment and the song is said to have been a staple of the Quarrymen.
The name Maggie May could be seen as a nickname for Mary Magdalene, and Edmunds gives ample newspaper reports of events similar to those portrayed in the song.