The earliest versions seem to be about going to Caledonia, not Canada.
And then these are based on an even longer song from the 18th century, (19 stanzas) called 'The Caledonian Maid'. This is in Fair Isabel's Garland in the British Library. Even in this the start of the story is a little sketchy and looks to be a survival from an even longer ballad. Her lover was Scottish in the army and had a commission to go back to Scotland. The next bit is confused. A troop of soldiers come by while they are taking their last farewells at which point the lover disappears mysteriously and she asks the soldiers to take her with them to Scotland offering pay. They agree intending to sell her as a slave in Scotland, but the sea? captain says no they'll kill us if we do this. At any rate we're told her lover already has a wife in Scotland. She asks the captain to disguise her as a sailor which he does and they travel to many lands. The captain has a dream in which he is told to marry her to save her. When he goes to find her in the morning the 'deceiver' has bound her hand and foot and ready to throw her in the sea. The captain and the maid have a long conversation and he offers to save her life if she will serve him when they come to Caledonia. In the later short versions c1800 he marries her.