There are many and varying versions of this great song. As far as I can trace,it first appeared in Popular Ballads and Songs (1806) by Robert Jamieson (c.1780-1844).
Jamieson got the song from Anna Brown, née Gordon, (c.1747-1810), the first Scots ballad singer to have her considerable repertoire collected. (I believe some academic is currently working on a biography of her. Anyone know any details?) She spent her childhood on an estate near Braemar (not far from Brackley, which was in nearby Ballater). Mrs Brown learned most of her songs from her aunt and her servants. Jamieson, from Morayshire, visited Mrs. Brown at her home in Dysart, Fife in 1800 and got numerous songs from her. He wrote, 'she learnt most of them before she was twelve years old; what she once learnt, she never forgot'. Sir Walter Scott also collected a version of the ballad, supplied to him by two female great-grandchildren of the man who killed John Gordon, the Baron of Backley, Farquharson of Inverey.
I seem to recall that Hall and McG sang 'through the woods of Glenturner'. Actually its Glentanar, a few miless east of Ballater.