It doesn't, though the words are essentially the same. Scottish spelling has never really been standardised, and stein, stane and steen are all used.

Andrew Lammie was a pretty popular song in its day, and the story is more or less true. "Temple stone" is not usual; it appears (so far as I know) only in Sheila (MacGregor) Stewart's set, which she learned from Jock Whyte of Aberdeen. Of course, other people may sing it that way, too; but all the texts I've found in a trawl of websites are obviously copied from hers, though mostly indirectly. I've only come across two examples that acknowledge her, and they use the more usual spelling "stane".