DMUK I went through about 2 years ago in NSW, so my experiences may not hold for your OH as things have changed in that time and some of my comments may be incorrect.
I needed to apply to the NSW board of studies for approval to teach. They wanted to see transcripts of my degree courses to see that my background knowledge was equivalent to those in Australia, and that I had done the right amount of university study. After I got approval to teach I was then able to apply to the NSW Department of Education and Communities and to the private education authorities as someone they might potentially emply. At that time, the DEC ran a 5 day Overseas Trained Teacher followed by a two week school placement course that I had to attend, but I think they have got rid of this course now. I also think that from now on (in NSW from the start of 2015?), prospective teachers have to apply to the AITSL rather than the NSW board of studies.
I am guessing it will be provisional registration initially. I had to do lots of paperwork with examples of how I met the teacher standards to change my provisional into a full registration, but NSW may be different.
All the best, but be aware there are many more teachers than jobs in many places at the moment ......