ive read somewhere that you still have to get oz qualifications via a skills test although like most places in the world you can find work with no local paperwork,
depending upon how soon your going to be leaving you can get an nvq via an osat if you contact the citb, takes a minimum of 10 weeks, obviously you must be working in the trade and you would need to build a portfolio asap, 8 units to pass, mechanical fixing, direct bond, working with basic working platforms, floating, setting, coving, floor screeding and optional units from flat render to dashing
if you did take an nvq you would be better to take it via city and guilds rather than edexcell, most people in construction prefer the logo
i think you need a tfn and abn and a blue card you can apply for this before you go, saves time heres a link for the blue card
http://www.peachinstitute.com/whsinfo.html