I found 2 versions of this in the Bodleian library's online collection.

The first is from Swindells (Manchester) who published broadsides between 1796 and 1853. Since it mentions Victoria, it is unlikely that it is before about 1825 or so, though she was quite a fashionable young lady before she became queen in 1837, so it could have been printed earlier than that. The second version, more or less exactly the same words as the first, was published by H. Such of 177 Union Street, Boro, London SE. Such published broadsides between 1863 and 1885, so it is certain that this was a copy of the Swindells broadsheet.

BLACK VELVET BAND (tune "Tars of the Blanch")

To go in a smack, down at Ba[r]king, when a boy, as apprentice I was bound
And I spent many hours in comfort in that pleasant little town;
At length future prospects were blighted, as soon you may all understand,
So by my downfall take warning – beware of a black velvet band.

One day, being out on a ramble, alone by myself I did stray,
I met with a young gay deceiver, while cruising in Ratcliffe Highway;
Her eyes were as black as a raven, I thought her the pride of the land,
Her hair, that did hang o'er her shoulders, was tied with a black velvet band.

She towed me in port and we anchored, from virtue she did me decoy,
When it was proposed, and agreed to, that I should become a flash boy,
With drinking and gaming and plunder, to keep up the game was soon planned,
But since, I've had cause to remember the girl with a black velvet band.

Flash girls, if you wish to turn modest, and decent connexion to gain,
Do not wear a band o'er your forehead, as if to tie in your brain;
Some do prefer Victoria fashion, and some their hair braided go grand,
Myself, I do think it much better than a girl with a black velvet band.

Young men, by my fate take a warning, from all those gay ladies refrain,
And seek for a neat little woman that wears her hair parted quite plain;
The subject that now I do mention, though innocent, soon me trepaun'd,
But still I've a strong inclination for the girl with the black velvet band.

For she towed in a bold man-of-war's man, her ogle she winked on the sly,
But little did I know her meaning, when I twigged her a faking his cly;
He said, I'm bound for the ocean, and shortly the trip will be made,
But still I've a strong inclination for the girl with the black velvet band.

A snare was invented to slight and banish me out ofher sight,
A fogle she brought of no value, saying, more I will bring this night;
She slipped it into my pocket, false girl! And took me by the hand,
They gave me in charge of the sneezer – bad luck to the black velvet band!

I quickly was nai[l]ed and committed, and cast in the jug for a lag,
For a wipe that she pinched and bunged to me, and valued no more than a fag;
The judge said to me, You are sentenced to a free passage to Van Diemen's Land,
Far, far away from relations so adieu the black velvet band.

What I hadn't realised, until looking at this version, is the similarity between this and other "rakes progress" style ballads including "Ratcliffe Highway".

Obviously, by the end of the century, this song has been transformed into a much tighter and shorter ballad similar to its modern form. I have a recording from the famous "Ship Inn" in the 1920s or 30s from someone who said his father sang it. It is to some extent intermediate between the broadside version and the modern ballad, though it resembles the modern version much more closely.

By the way, I think this is one of the few completely traditional songs now sung as everyone who I know sings it has certainly learned orally. Very few would take the trouble to learn it any other way, I think.

For those whose geography of Essex isn't too good, Barking is a medium sized town in the part of Essex now within Greater London. Ratcliffe is nearby. ^^ Cheers! IanC