Here you are, from the National Library of Scotland! So it seems the song was about Burns' Highland Mary, although not written by him.
http://digital.nls.uk/broadsides/broadside.cfm/id/20798
Various recordings of it, including John Cormack, but I particularly remember Kenneth McKellar doing it.