If you don't know already, get a doctor to check you for diabetes and colour blindness. You can find the medical standards required on the JAA site. Look for
JAR-FCL 3.
If your goal is to ultimately get a JAA or EASA licence then study LASORS from the UK CAA's site.
To find out what the requirements are in Australia, read
here. CASA is the Australian regulator. PPLs are fairly easily transferred from one ICAO state to the other.
So, where to go? All major capital cities have flying schools. Oxford has just recently bought GFS in Melbourne. In Perth, there is a JAA accredited flying school.
Personally, I'd go to where you want to go. Build some hours and have a holiday. Perth's great and Minovation's boss is British and knows both systems pretty well. (her PPRuNe nick is Charlie Foxtrot India)
Contrary to popular belief, the wx in Australia can be a challenge and navigation in the outback will really test your skills. Assuming you leave the GPS at home. There's other things to think about when flying in Australia. Remote area considerations and regulations. There is also controlled airspace too. etc.
Look for a good instructor who'll follow the syllabus, instil good airmanship and have fun too. The PPL is for fun.
It's the rest that becomes hard work...