Assuming you don’t have an exemption due to marriage, PR status or a working holiday visa (or one of the few other ways to get an exemption, which may soon include being a “special foreigner”), the answer varies depending on the kind of job.
Someone else will probably list the usual requirements soon (I’m too lazy). For a definitive answer, the company should ask the Workforce Development Agency.