Some very early mentions:

1856 William Jackson Palmer, "Diary," in John Stirling Fisher, A Builder of the West: The Life of Gen. William Jackson Palmer (Caldwell, Ida.: Caxton, 1939), p. 49: "[May, 1856]…A short favorable run of 20 hours would 'tie us up by the nose' in the North River, or, as the sailors say in their songs, 'Run her into clover.'…[The sailors' songs are] musical but after a certain wild mood that is very appropriate to the words and the scene:
        "Hi, yi, yi, yi, Mister Storm roll on, Storm Along, Storm Along," … "All on the plains of Mexico,"… "Aha, we're bound away, on the wild Missouri."