Ten Thousand Miles Away (in the DT) is the parent of this parody by Carryl, as has been noted. The Bodleian Library has a broadside of "Ten Thousand Miles Away" that is dated between 1840-1866, Ballads Catalogue, Harding B 11 (3763), J. Harkness, printers, Preston.
Hugill's estimate of early 19th century is a little early, since the chorus mentions the morning train, so I would guess 1860 approx. I would also guess that the song is English; I think Hugill suggested Irish. Bob Bolton mentioned that Australia is ca. 10,000 miles from England, and that there is a version in Australia. In the first verse, "my true love so gay .... She has taken a trip on a government ship,...." (Transportation for offenses?).

Carryl's parody, "A Capital Ship (Was Walloping Window Blind)" is, of course, later, but so far I can't find the date. It is discussed, with Carryl's and one other set of words, in thread 24814, linked by Masato, above.

I remember happily singing this song in grade school, ca. 1930. One of the few I remember (along with "Little Brown Cheursche in the Vale"- we loved messing up that song to the despair of the music teacher).