Hairdressers always seem to be in demand, especially UK trained ones :)
As for gardeners in April/May - that is when winter sets in so there will be rain, the grass will be growing and will need mowing throughout the winter season, in fact everything will be growing and in need of all sorts of attention. Winter is the 'easy' season on plants here when they get most of their growing done, summer is the 'stress' season when they hang on tight and just try and make it through.
I can't really help you with how to get going as a business, unless you want to buy a Jim's Gardening franchise, but I think the time of year will be a bonus rather than a problem.
All the best with your move!
PS have you noticed this forum is moving - you might be better posting your questions on
http://www.adelaide-brits.com as very shortly there won't be much activity on here...