"Shenandoah" appears to have originated with Canadian and American voyageurs or fur traders travelling down the Missouri River in canoes.

By the mid 1800s versions of the song had become a sea shanty heard or sung by sailors in various parts of the world.

Lyrics from prior to 1860, as given in Sea Songs and Shanties, collected by W.B. Whall, Master Mariner (1910,) were reported as follows:

Missouri, she's a mighty river.
Away you rolling river.
The redskins' camp, lies on its borders.
Ah-ha, I'm bound away, 'Cross the wide Missouri

From Wikipedia