"Mary of Argyle" appeared in sheet music as "Mary of Argyle, with variations, op. 211" by Charles Grobe, 1852; Couenhoven, Scull & Co., Philadelphia. In the folio the melody was subtitled "Melodies of the People, no. 5."
Other sheet music for piano, James Bellak, again without lyrics, is dated 1855.
(The above at American Memory)

The sheet music at Levy Sheet Music, cited by Malcolm Douglas, is dated 1864, printed George Dunn, Richmond, VA (date in fine print on the cover).
There were several unattributed song sheets published by De Marsan, Andrews etc. (American Memory).
All copies at American Memory were printed in the U. S., although the melody is called "Scotch" on one or two.

The Bodleian Library has several undated sheets, no author cited, printed in England, which they attribute to Charles Jeffries.

The National Library of Scotland, The Word on the Street - http://www.nls.uk/broadsides/highlights_ballads.html - comments:
"Bonnie Mary of Argyle" is one of the best-known of Scottish ballads. It was written by two Englishmen, Charles Jeffries (1807-1865) (words) and Sidney Nelson (1800-1862) (music). It is not known when it was first published - possibly during the 1850s."
"The Mary in question was Robert Burns beloved 'Highland Mary' (Mary Campbell, 1763-1786) born in Dunoon. ....."
The broadside was published by James Lindsay, Glasgow (a late printing, 1860 or later).
Highlights