Edward Ellis Morris (1843-1902), English educationist and author, defined the names Bananaland and Bananalander in Austral English: A dictionary of Australasian words, phrases and usages, with those Aboriginal-Australian and Maori words which have become incorporated in the language, and the commoner scientific words that have had their origin in Australasia (London, 1898):

Banana-land, n. slang name for Queensland, where bananas grow in abundance.
Banana-lander, n. slang for a Queenslander (see above).

The following definition of Queensland is from Oxford Dictionaries:

A state comprising the north-eastern part of Australia. Originally established in 1824 as a penal settlement, Queensland was constituted a separate colony in 1859, having previously formed part of New South Wales, and was federated with the other states of Australia in 1901.

The earliest instances of Bananaland that I have found date from 1880.

Notes from Bananaland was the title of the Queensland section of The Bulletin (Sydney, New South Wales) from Saturday 30^th October 1880 to Saturday 14^th May 1881—according to what I have found.

And the following story is from The Meddler, published in The Sydney Mail and New South Wales Advertiser (Sydney, New South Wales) of Saturday 4^th December 1880:

Genuine bravery is rare as are good wit and good wine. Years pass, and the wide world gives us no instance of stalwart heroism that seems worthy of being placed on record; nothing that stirs us up as Casabianca¹ and Horatius² used to do, as the Loch Ard and Tom Pearce³ episode did, even as a little story briefly related in the last week’s Queensland telegrams did. Five boys were bathing in the Brisbane River, one swimming, his mates in the shallows; a black demon of a shark went for the morsel of white flesh floating so temptingly above him—a long black, hungry demon, with jaws agape and back fin cutting the water. The lads in the shallows saw the danger, and ran home screaming, you may surmise. Surely it was the natural course; but there was something altogether unnatural in the pluck of these lads. They dashed out into the water with yells and shouts, they fought around the monster, and dragged their comrade torn and bleeding from his jaws. Too late, alas! They tell us he has died since. Too late for the practical success they merited so well, yet surely not too late to have earned the applause of every man who holds a spark of fire within his body of clay. Have you ever seen the jaws of the black sea demon agape as he rises through the water for a final rush? If so, you will understand that those Brisbane lads faced danger before which a Badajos or Balaklava hero might have quailed. You will rejoice in the proved pluck of the young Bananaland, and say the good old blood throbs strongly within us yet.

¹ Casabianca (1826), by the English poet Felicia Dorothea Hemans (1793-1835), is about a boy who, during a naval battle, refuses to desert his post on a burning ship and perishes when it explodes.
² Horatius, from Lays of Ancient Rome (1842), by the British author and politician Thomas Babington Macaulay (1800-59), is a poem about Publius Horatius Cocles, an officer in the army of the ancient Roman Republic, who defended the Pons Sublicius, a bridge of Rome, from an invading army.
³ This is a reference to the British ship Loch Ard, which was wrecked off the coast of Victoria, Australia, in 1878; one of the two survivors, Tom Pearce, saved the other, Eva Carmichael.

The earliest instance of Bananalander that I have found is from the cricket section of the Queensland Figaro (Brisbane, Queensland) of Saturday 12 May 1883:

We hope next season to see a marked advance towards the preparation of such wickets as they have in Sydney and Melbourne. It is ridiculous that only one Club in the City of Brisbane should have a respectable wicket, and that a suburban one. Cannot some arrangement be made, during the recess, to improve Queen’s Park. The Clubs all appear anxious to do so, but insecurity of tenure is the stumbling block, and has prevented the expenditure of the requisite cost of improvement. Meanwhile, they, instead of uniting and trying to obtain a right to prepare wickets without risk of interference, potter away serenely in the same good old style of their forefathers. The enthusiasm which prompts the Bananalanders to predict that it is the coming colony of Australia, should stimulate its Cricketers to efforts to prepare wickets, such as will secure bowlers immunity from a charge of manslaughter.