You can get from the US to New Zealand nonstop via three airlines: Air New Zealand, United, or QANTAS.

Air NZ and United are both in Star Alliance (referred to as *A around these parts), so if you start a United Mileage Plus account you can redeem those miles for tickets on either airline.

QANTAS is in OneWorld Alliance along with British Airways and AA, so your AAdvantage miles can be redeemed for QF tickets. (Many QF flights also carry AA flight numbers, but even so you'll still be riding is a big red-tailed 747 with a kangaroo on it!)

Your strategy should consider which airline you'd like to fly to NZ (each has its defenders, but Air New Zealand is really very nice); which program you can earn miles in most quickly; and award availability (seats are always limited, esp. in the "summer season" down under).

As you've already figured, buying airline tickets is only one way to earn miles -- and not necessarily the fastest. I'm going to make a suggestion that might sound odd: consider joining the British Airways Executive Club and getting a Diners Club card. DC awards 24,000 bonus Club Rewards points over the first year of membership, plus two points for every dollar you spend... and each summer for the last several summers DC members have been allowed to transfer Club Rewards points to BA Executive Club accounts on a one-for-one basis... PLUS most of your paid American Airlines travel (except for very cheap discount tickets) can be credited to your BA account...

... and BA Executive Club points can be redeemed for QANTAS award seats thanks to OneWorld. What's more, award availability through BA has been generally very good in my experience, though planning well in advance is a plus.

Others here will have other ideas. Welcome to FlyerTalk!