Yes, your company would probably need to be registered in the US. You'd need to get H1b visas for your employees as contractors for your client. This is a fairly standard process that a lot of consulting firms (like Infosys, Wipro, Tata - all from India) follow.
However, if you're small, this, coupled with legal fees for the visa process and the time/quota restrictions on H1b visas, may be a significant overhead for your business.
You should probably talk to a US immigration attorney and see if there are other options. You can go the L-visa path, but it limits your employees to only work on-site of your US subsidiary (you'll still need to register in the US). While some consulting firms put L-visa people on clients' site, this is technically illegal, and the DOJ is investigating the aforementioned companies for violations of this kind.
If your employees can work for your US client from Australia/New Zealand, that would make it much easier for you. You don't need any permission from the US government to work for US clients as long as you're not doing it on the US soil. For occasional meetings you can go to the US with a regular WVP or B1 visa.