Pepys didn't hear it in Scotland, as I've told Boab before. He heard it in London, at Lord Brouncker's house, January 2 1666, sung by Mrs Knipp, an actress of whom he was rather fond. It was probably a stage song, and quite new at that time.

Pepys described it in his diary as a "little Scotch song" which, as William Chappell pointed out more than a century ago, was descriptive of style, not provenance; similar songs had been called, generically, "Northern" (for which, read "rustic") before the accession of the Stuart dynasty led to a change of fashion and terminology.

No broadside edition survives from Pepys' time; the earliest copies we have were printed in London. The song may have started out in England or Scotland; we don't know, though the former would seem more likely on the whole. I think that all this has been said in earlier discussions here (see list above).

I assume that Ian P meant "recorded" in the usual, broad sense and so was not asking about the earliest sound recording; but perhaps he would clarify that for us.