I hate to be the barer of bad news, but I'm afraid that primary teaching has been taken off the skilled migrant category list. The jobs out here are VERY limited, and the Government is currently being heavily criticized for putting a lot of money into boosting teaching numbers (through university degrees being funded, and through bringing in teachers from overseas), but now there are more teachers than jobs.
Having said that, some people are certainly in the right place at the right time, and mange to walk into a job pretty quickly.
Best advice is that, if you do decide to come out here, be prepared to do a lot of relief teaching day-by-day, and a lot of knocking on doors. It could take a few years to get a regular job.
Sorry for the potentially bad news, but I hope this answers your question