Thanks, Peace! In sum so far:

"Two Soldiers" is a traditional song from the American Civil War, collected in Kentucky and Arkansas. It seems likely that Jerry Garcia learned it from a 1964 Mike Seeger recording (it was also recorded in 1973 by Hazel Dickens and Alice Gerard--Mike Seeger's wife).

From Ballads and Songs, Belden (with minor corrections). Collected by Ruth Sedwick in 1912 with the notation that it was "learned twenty-seven years ago in the Taney County hills."

So now we've Kentucky, Tennessee and Missouri (Taney County); Civil War origin and 1885 Missouri provenances. I recall Creighton citing the Crimean War.