This is most likely some poetic license on the part of the song's creator; it's difficult to reconcile Tolkien's drafts with a situation where the Moon is in the sky, but unstained, before the awakening of the Dwarves, and is then stained later. But we can assume a literal interpretation, and it actually makes more sense than you'd expect, though it's not perfect.
What "stain"?
If it refers to anything at all, it likely refers to this event (emphasis mine):
Now Varda purposed that the two vessels should journey in Ilmen and ever be aloft, but not together; each should pass from Valinor into the east and return, the one issuing from the west as the other turned from the east. Thus the first of the new days were reckoned after the manner of the Trees, from the mingling of the lights when Arien and Tilion passed in then- courses, above the middle of the Earth. But Tilion was wayward and uncertain in speed, and held not to his appointed path; and he sought to come near to Arien, being drawn by her splendour, though the flame of Anar scorched him, and the island of the Moon was darkened.
The Silmarillion III Quenta Silmarillion Chapter 11: "Of the Sun and Moon and the Hiding of Valinor"
This story wouldn't enter the narrative until after Return of the King was written, however, so it's difficult to reconcile.
But...what moon?
Interesting to note is that there are versions of the Legendarium in which the moon predates the awakening of the Dwarves; in one of these drafts, which Christopher Tolkien dates to around 1946-1948, the moon is actually a product of Melkor's petulance:
[T]he Earth may not be wholly destroyed against its fate; nevertheless Melkor took a portion of it, and seized it for his own, and reft it away; and he made it a little earth of his own, and it wheeled round about in the sky, following the greater earth wheresoever it went, so that Melkor could observe thence all that happened below, and could send forth his malice and trouble the seas and shake the lands. And still there is rumour among the Eldar of the war in which the Valar assaulted the stronghold of Melkor, and cast him out, and removed it further from the Earth, and it remains in the sky, Ithil whom Men call the Moon.
History of Middle-earth X Morgoth's Ring Chapter 1: "Ainulindalë"
As well, earlier versions of the awakening of the Dwarves places their first appearance well into the First Age, after the creation of both the Sun and the Moon:
- About this time the Gnomes climbed Eredlindon and gazed eastward, but they did not pass into the lands beyond. In those mountains the folk of Cranthir came first upon the Dwarves, and there was yet no enmity between them, and nonetheless little love. It was not known in those days whence the Dwarves had origin, save that they were not of Elf-kin or of mortal kind, nor yet of Morgoth's breeding.
History of Middle-earth IV The Lost Road and Other Writings Part Two: "Valinor and Middle-earth before The Lord of the Rings" Chapter III: "The Later Annals of Beleriand"
There's nothing said of when the Dwarves first awoke, but it does at least admit the possibility that it was after the rising of the Moon.
Both of these drafts were written around (or shortly before) the writing of The Lord of the Rings, and it's likely that they were in Tolkien's mind when he penned Durin's song.