It appears that the attribution to Jean Glover (for which Burns was responsible) is nowadays considered doubtful.  Certainly, the tune seems first to have been published, as O'er the Moor amang the Heather, in 1758, the year she was born, and appeared in a MS of 1740.  This information from Bruce Olson; on his website he further notes:

"O'er the Moor amang the Heather ['In the Moor among the Heather' in P. Thompson's Twenty Four Country Dances for the Year 1758, p. 11, and with Bremner's title in another such by R. Bride for 1769, p. 51.  These have same tunes but different dance figures.]; RBR 77: [?]; NSR 9: Aldavaligh or O're the moor among the Heather; AMR 24"

A little more poking around in the Forum resulted in the following:

Skippin' Barfit through the Heather  Text and tune from Alison McMorland, who learned it from Jessie Murray of Buckie.  I posted this one myself, but had forgotten about it.

Queen Amangst the Heather  Suzanne (SKW) quotes some comments made by Hamish Henderson, who traces the song back to Glasgow Peggie (Child #228), the story of which is vaguely similar.  Henderson points to similarities in the tunes that carry the two songs.

Heather on the Moor...anyone?  Bruce Olson quotes the text from the Scots Musical Museum (1792), with comments on the antecedents of song and tune.

heather on the moor  Text as noted by Burns, with info from Bruce.

For the sake of completeness, I'll repeat links to the DT files that George has already pointed to, using relative URLs for times when the main server is down:

DOON THE MOOR (2)  From Colm O Lochlainn's More Irish Street Songs; with tune.

DOON THE MOOR  No source named or tune given.

HEATHER ON THE MOOR  From Dan Milner's Bonny Bunch of Roses.  No traditional source named, though two tunes are given, unfortunately unidentified.

A set of O'er the Muir Amang the Heather/ Aldivalloch, transcribed from the Skye Collection by Wendy Galovich, can be found at  JC's Tunefinder.  It is identical to that given in Niel Gow's Repository of the Dance Music of Scotland, book I, (c. 1799) and probably derives from it.