Wow! I've had a ball reading through this thread today. I've recently discovered this melody (yes, I live a secluded life) and have recently been looking fervently for a definitive version of the lyrics. However, I have had no luck in such a search until I found this thread. Here I found a bunch of variants and I picked versions and stanzas that struck my fancy. After much borrowing and stealing and adding my own interpretation of the story I came up with the following lyrics. Nothing earthshattering here but I like this one a lot. I do it in couplets with breaks in between. My $.02:

Now the Missouri is a mighty river
Away, you rolling river
And you'll find Indian camps along her border
Away, I'm bound away
'Cross the wide Missouri

'Twas there I fell in love with a beautiful keegsquaw
Away, you rolling river
She was the daughter of Chief Shenandoah
Away, I'm bound away
'Cross the wide Missouri

It's been seven years since first I knew her
Away, you rolling river
Now she's in full bloom for a man to woo her
Away, I'm bound away
'Cross the wide Missouri

Oh Shenandoah, I've come to see you
Away, you rolling river
Oh Shenandoah, may I speak with you
Away, I'm bound away
'Cross the wide Missouri

Oh Shenandoah, I love your daughter
Away, you rolling river
I want to take her 'cross yon rolling water
Away, I'm bound away
'Cross the wide Missouri

Oh Shenandoah, with gifts I'm laden
Away, you rolling river
Please give me the hand of this fair maiden
Away, I'm bound away
'Cross the wide Missouri

Then Shenandoah said you must forsake her
Away, you rolling river
For an Indian brave has come to take her
Away, I'm bound away
'Cross the wide Missouri

Oh Shenandoah, I'll not deceive you
Away, you rolling river
Farewell my love I'm bound to leave you
Away, I'm bound away
'Cross the wide Missouri