Aside from the version you posted above from April 1868, the only version I've found remotely cracking that date was from August 1868 in Brooklyn Daily Eagle, Aug. 14 1868, p. 4:

"Rio Grande," is perhaps the greatest favorite of this description of songs [shanties with an "air of romance"], but all the beauty lies in her mournful air:--
 To Rio Grande we're bound away, away to Rio;
 Then fare you well, my pretty young girls,
  We're bound for the Rio Grande."

Though I should note that at this point in time "Shanandore" and "Rio Grande"/"Rollin' Rio" were considered two different songs, as reported in several journal's reprinted "Songs of the Sea":

The meter [of windlass songs] is apt to be shorter, as the motions are quicker. "Shanandore" is a famous one:

 "You Shanandore,
 I long to hear you."
   Chorus--"Hurrah! you rollin' river."
 Yon Shanandore, I long to hear you."
   Chorus--"Ah, ha! you Shenandore."

Another is "Rolling Rio," and a true favorite is this:

 "For seven long years I courted Sally."
   Chorus--"Hurrah, you rollin' river!"
 "I courted Sally down in yon valley."
   Chorus--"Ah, ha! I'm bound away on the wild Missouri."

(A second article attests to this separation in 1892).

The first place I found the two songs tied as having a common origin, The San Francisco Call, June 4th, 1911, wrote that they were not said to have originated "The negro roustabout on the Mississippi river [sic]" rather than the armed forces. That version does have a rather lengthy and flowery version of Shenandoah which mentions a "Yankee clipper," but the implication here seems to be the American Yankee rather than the Northern.

All this to say, I think we can rule out the song originating in the Civil War. You write it could have been from the Mexican-American War above, which remains in the realm of possibility.

The earliest reference to the song's association with the armed forces I've found comes in 1915, in a story about the training of the 1st Cavalry of the Illinois National Guard, via Floyd P. Gibbons for Chicago Tribune. He implicated the song was sung "by the Seventh United States Cavalry during the years that it was in Indian service along the Missouri river." Here, the lyrics are:

For seven long years, I courted Nancy.
Hi-oh, the rolling river.
She wouldn't have me for a sweetheart.
Ha, ha. We're bound away for the wild Missouri.
Because I was a cavalry soldier.
Hi-oh, the rolling river.

A drinkin' rum and chaw terbacker.
Ha ha. We're bound away for the wild Missouri.
And then she went to Kansas City.
Hi-Oh, the rolling river.
She must have had another sweetheart.
She wouldn't have me for a sweetheart.
Ha, ha. We're bound away for the wild Missouri.
Because I was a cavalry soldier.
Hi-oh, the rolling river.

This version matches closely the rendition in American Folksongs from John Minear's post, but precedes it by nearly 2 decades.

The American Indian Wars mostly precede the Mexican American War, but without specific battles, it's difficult to date just how long the 7th Cavalry reportedly was singing this before the Mexican-American War. The 7th formed in 1866, immediately following the Civil War; the bulk of the Indian fighting west of the Mississippi ended in the 1880s, giving us a probably date of the 1870s, but skirmishes persisted until the early 1900s.