Just to secure this song, the earliest mention I find of it is seagoing.
General William Jackson Palmer is sailing back from England in 1856. He tells of the sailor's chanteys (or shanties) during the voyage "'Hi, yi, yi, yi, Mister Storm roll on, Storm Along, Storm Along,' or 'All on the Plains of Mexico,' or the wildest and prettiest of all, which ends - 'Aha, we're bound away, on the wild Missouri.'"

A builder of the West; the life of General William Jackson Palmer, John Stirling Fisher, (Caxton printers, 1939) 49