AeroDMB,
I'm pretty sure that unless you have an FAA ATP you'd need to do all 5/6 ATP exams and the IR exam. Along with the CPL and IR flight test. If you do have an FAA ATP, all you need to do are Air Law, Human Factors and the IR exam and maybe the IR flight test.
This is what was needed 6 months ago. but CASA (think FAA but nazis) are in the process of changing things.
As far as getting a job is concerned, it's no different fom working here. If you have the right to live and work in Oz, you can apply to any of the airlines. I know of a few Americans that fly for Qantas but they're married to Australians.
Good Luck,
Kenny