The song certainly began life as a broadside, though I can't say when.  Such and Pitt both issued it; copies can be seen at  Bodleian Library Broadside Ballads:

The lads of Virginia  Printed between 1863 and 1885 by H. Such, Machine Printer, & Publisher, 177, Union- street, Boro'., S.E. [London]

The lads of Virginia  Printed between 1819 and 1844 by Pitts, Printer, wholesale Toy and Marble warehouse, 6, Gt. St. Andrew Street, Seven Dials [London]

George B. Gardiner and Chas. Gamblin noted a set from Mrs. Goodyear of Axford, Hampshire, in 1907, so the song was certainly circulating in oral tradition at that time, though I think it has only been found twice in Britain.  Barry, who posted a longer text in the thread Masato has pointed to, named no source for it, but said that it dated "to pre 1775", though he offered no evidence.  It probably came from a broadside, being quite close to those mentioned above.

Of the Hampshire set (which is the one Martin Carthy recorded, though he edited it in places so that it made better sense), Frank Purslow (Folk Music Journal, Vol. I no.3, 1967) commented:

"This rather corrupt, and presumably incomplete text is the only one I have seen, although it is certainly of broadside origin.  The metre is unusual and gives the impression that there should be two more lines to each verse.  Dr. Gardiner draws attention to the "local mannerism" in the tune: the first two notes in the seventh complete bar and the last two notes.  This occurs often in Mrs. Goodyears's tunes and in those of other singers in the area. "

VIRGINNY

(Noted from Mrs. Goodyear of Axford, by Basingstoke, Hampshire, in 1907 by George B. Gardiner and Chas. Gamblin)

Come all you young fellows wheresoever you might be,
Come listen awhile and I'll tell you,
There's many a young fellow myself I have seen,
More fitting to serve Victoria our Queen;
But those hard-hearted judges so cruelly has been,
For to send us poor lads to Virginny.

When we arrived in Virginny, that old, ancient place,
Which now I renown in my story,
Our captain he stands with a rod in his hand,
To bargain for us like slaves out of bond,
When he saw those young fellows a-ploughing the main,
How hard was my fate in Virginny!

Old England, old England, I shall never see no more,
If I do, it's ten thousand to twenty,
For my fingers are rotting and my bones they are sore,
I wander about, I'm brought down to death's door,
But, If I only live to see seven years more,
I will then bid adieu to Virginny.

A midi of the tune made from Chas. Gamblin's notation goes to  Mudcat Midis;  in the meantime it can be heard care of the  South Riding Folk Network  site:

Virginny.mid

The other example was recorded from Bob Hart of Snape, Suffolk in 1973, by Tony Engle (and, a few years earlier, by Rod and Danny Stradling); by this time it had become Australia rather than Virginny, but it's recognisably the same song, though much changed (Steve Roud's Folksong Index actually assigns it a different type number).  It has also been recorded from Percy Ling and Cyril Poacher, but they all used to hang out in the same pub, so it can be treated as a single variant for practical purposes.

AUSTRALIA

(Noted from Bob Hart of Snape, Sussex in 1973 by Tony Engle)

Come all you young fellows, wheresoe'er you may be,
Come listen awhile to my story.
When I was a young man, my age seventeen,
I oughtn't a' been serving Victoria, our queen,
But those hard hearted judges, oh how cruel they be,
To send us poor lads to Australia.

I fell in with a damsel, she was handsome and gay,
I neglected my work more and more every day;
And to keep her like a lady I went on the highway,
And for that I was sent to Australia.

Now the judges they stand with their whips in their hand,
They drive us like horses to plough up the land;
Youi should see us poor fellows, working in that jail yard,
How hard is our fate in Australia.

Australia, Australia, I would ne'er see no more,
Worn out with the fever, cast down to death's door;
But should I live to see, say, seven years more,
I would then say adieu to Australia.

This text was published in Everyman's Book of English Country Songs (Roy Palmer, 1979).  Palmer commented:

" The loss of the American colonies deprived the British Government of a place of exile for convicts.  As an alternative, transportation to Australia was started in 1787.  It was successively abolished by New South Wales (1840), Van Dieman's Land, which changed its name to Tasmania at the same time (1852), and finally by Western Australia (1868).

Historians differ as to whether transportation was a severe punishment for convicts, or a favourable opportunity for them to begin a new life, but the popular tradition is unequivocal: for many generations after its abolition, songs and stories continued to express the people's fear and loathing."

A midi of the tune made from the notation in the above book goes to  Mudcat Midis;  in the meantime it can be heard care of the  South Riding Folk Network  site:

Australia.mid  The first verse is two lines longer than the others, which begin at the third line (9th bar).

It has been suggested that at least some transportation songs were a conscious affort by the authorities at deterring crime; an exaggeratedly horrific picture was painted in order to frighten potential offenders.  I have no idea if this is true, but it is an interesting thought.

Though largely forgotten now, this song must have been reasonably well-known in order to have been found, sung to the same tune (though changed) in Hampshire and Suffolk sixty years apart.  As to whether the text in the older thread is traditional in whole or in part, I can't say, but it is certainly the case that the song entered oral tradition at some point and persisted in it for at any rate a century and a half.