Fowke claimed that the song developed in 1869 at the time of the Red River Rebellion (Canadian Encyclopedia): Encyclopedia

A very popular website, www.homestead.com, says the song originated among British troops who came to Manitoba through the Northern Red River Valley. "It was a military song."
In the next paragraph, this website says the song "is believed to have been written by James Kerrigan in 1896." This of course is impossible if the song is, as Fowke believes, some 25 or so years older.
The website has an excellent midi, with a slightly variant chorus, and very attractive illustrations: Red River Valley
Not carrying the investigation forward, but interesting.