I am looking to travel to Brisbane, AU for a period of 3-6+ months. I can obtain a work-holiday visa; but how easy is it for someone to make it a working holiday, especially without prior experience and without a university degree?
Don't worry. Finding temporary unskilled jobs in Australia is easy, the economy is booming and Australians don't want to do them so hostels, cafes, restaurants, ski resorts, farms etc rely quite heavily on cheap, seasonal backpacker/working holiday labor.
As Mark says, the easiest thing is to simply ask around at your hostel after arrival, but also take a look at Gumtree to get an idea of the type of jobs and wages on offer.