Retired couple just starting to plan an extended trip to New Zealand and Australia. We are thinking 90 days to split between the two countries, maybe 30 days in New Zealand and the rest in Australia. We wanted to leave in mid to end of February. My hubby loves to explore wine areas, I would like to see the Barrier Reef besides the "must see cities" in each country. Looking for experienced travellers in that neck of the woods to give us suggestions on where we should start and travel so we do not get ourselves in trouble with the weather (rainy seasons, or too cold in May/June timeframe for that area of the country).
Do study historical weather data before you finalize anything. Cairns is best visited towards the end of your proposed window to avoid the last of "The Wet" and to assure good weather, and clear water, for the trip out to the reef.
Suggest spending as much time on the South Island as possible, especially Queenstown and Christchurch. Best weather for that would be at the beginning of your trip, ie Feb and March. Anything much later and you'll be getting into late Autumn and early Winter with the risk of poor weather. Queenstown in particular is worth a week or more. Makes a good base for day trips to Milford Sound and Te Anau, there's gorgeous hiking everywhere, and it's truly one of the most beautiful areas on earth.
From Christchurch suggest a few days out on the Akaroa Peninsula, about an hour east of the city. Most of NZ is a delight to the senses, but those two areas were our personal favorites.
Sydney is nice any time of year, and the central attraction is one of the world's most beautiful harbors. They sell a weekly pass that covers the ferries, buses, and trains which is a terrific deal, and effectively makes the ferry system your own "hop on, hop off" service that you can use to explore all of the pretty little harborside neighborhoods.
Know too that the shoulder season in Hawaii is May to early June - can get some very good deals on resort hotels on your way home.
as suggested you might not want to be too far south (NZ) as the weather get colder. whereas 'most' of the east coast of Australia can be beautiful in April/May. Not too hot and over most of the humid days of Feb/March. If you are looking for wine areas then there are plenty to pick from. About 2 1/2 hours drive north of Sydney is the Hunter valley, home of award winning vineyards. There is plenty to see within a few hours drive around Sydney ( in all directions) but be prepared to fly to other states to see iconic sights as the drive can be too much, unless you are thinking of a motor home etc.
If you spent 'say' a month in NZ and the remainder in Australia, that should allow you to see a lot of territory, in both countries. And with the low Australian dollar , it is a good time to visit.
When we visited the US we stopped over in Hawaii both ways. We really enjoyed it and made the flights OK time wise.
Further thoughts regarding the planning for your trip: for getting around Australia once you're there, suggest looking at Jetstar.Com ...they're the local low-cost airline, and can provide an economical way to string together an itinerary from Sydney to any of the other Aussie destinations that might be on your list. Come to think of it I believe they have flights to/from New Zealand as well, including direct flights connecting Queenstown and Sydney.
I've only been down that way twice. The second time only to New Zealand. I really enjoyed the Waitomo caves, Rotorua, the Tongariro National Park and Bay of Islands. The second time I went was in February and the weather was usually sunny and 75-85. Also rented a car, which of course was stick shift and with driving on the left side of the road, especially after the long flight, created some laughs. I remember thinking that it felt exactly like when I first learned to drive and I turned on the windshield wipers instead of the turn signals a few times.
I live in Australia and have visited NZ, agree with most of Roberts suggestions wholeheartedly. I avoid Jetstar like the plague if there are any other options though. Tiny seats, often don't recline, no service, often no cheaper than Virgin, but for shorter 1 hour flights it probably doesn't matter.
That aside, I would suggerst NZ first than start in southern Aus and head north.
In New Zealand the North island has more Maori culture - try to fit in a maori evening with meal. We went to Te Puia which had a performance, meal walk down to watch the geyser and hot chocolate sitting on the thermal rocks near the geyser. It was awesome. We loved Waitomo caves, rotorua, really loved Taupo (if you want to get in a thermal pool it is heaps nicer in the creek in Taupo than in rotarua), but the best stuff is in the south island. I was very underwhelmed by the glaciers - if you have seen others I wouldn't bother. Queenstown is great, worth a few days. I would strongly suggest you don't try milford sound as a day trip from Queenstown - it is a very long day spent mostly on the bus. If you are not hiring a car for the rest (you should - New Zealand is lovely to drive) at least hire a car and stay overnight at Milford or Te anau. There is nothing at all at milford other than the boat trip (which is stunning), but the drive in is absolutely beautiful with lots of easy stops. I had read a lot prior to our trip to suggest the road was dangerous with lots of accidents, but we did it in july in the dead of winter and there was nothing dangerous about the road, its a lovely drive. I also like Dunedin and specifically the Otago peninsula - another lovely drive, walk on the beach with fur seals watch the penguins come in from a days fishing to nest, the albatross centre etc.
In Aus, it is harder to give advice as what I like as a local is probably very different to tourists. Melbourne is nice, good cafes. Sydney is all about the harbor (catch a ferry from circular Quay to Watsons bay for lunch), the ferry across to Many is also good. Tourists like Bondi Beach, but having grown up in Sydney it wouldn't even make my list of top 20 beaches in Sydney.
The barrier reef is lovely, and if you are into snorkeling worth the trip, but it is obscenely expensive. Head north to Cairns and try the kuranda railway (one way on the train and the return on the skyway). Queensland is lovely in May/June - you can get cyclones around Feb, and too many stingers over summer.
If money is no object, include Uluru and Northern territory, but it would require some expensive internal flights as it is about a 6-7 day drive from Sydney, driving all day.
Regardless of what you do, you will have a great time. When planning just keep in mind the distances. Australia is huge, and although New Zealand is small, it has a hell of a lot of mountains and is so beautiful, you will want to pull over and take a million photos every 2 minutes
One publication to include in your pre-trip planning is "Back Roads Australia", published by Eyewitness Travel and available on Amazon. As the title suggests it contains information on scenic drives throughout the country, including directions to some off-the-beaten-track places and attractions that you might otherwise overlook. Can help you organize an itinerary according to your interests.
Have never seen anything similar for New Zealand, probably because virtually every drive in NZ qualifies as a scenic drive.
Slavender is right about Jetstar - it's a spartan, no frills carrier...but it is cheap.
Distances in Australia really are vast, so would suggest flying between the major cities and then renting a car from there to save travel time.
Although Sydney and Melbourne get most of the attention, Brisbane and the Gold Coast are worth a look, as are Adelaide and Perth.
Be aware that it's a full day's drive from Alice Springs to Uluru, and accommodations near the rock are quite expensive. Worth it though, IMO, as one of those "once in a lifetime" experiences.
I agree with suggestions you head to NZ first. Firstly you will avoid some of the hottest weather in southern Australia and avoid 'the wet' in Queensland. As you have a reasonable amount of travel time, I would suggest you fly to Cairns from NZ and work your way south to Sydney. The Hunter Valley north of Sydney is a famous wine growing region. If it's wine growing regions and wine you are interested in head to South Australia and spend some time in the world famous Barossa Valley and McLaren Vale wine growing regions.
Cheap flights between capital cities Jet Star or Virgin are recommended. If you decide to spend some tine in Adelaide/South Australia please feel free to contact me. Our daughter lives in the Barossa Valley, so I will be able to give you some 'insider' information.
Your headline, although not the body text of your question, referred to Hawaii stopovers. I speculate you are thinking back a couple of decades (or more) when mid-Pacific refuelling stops were common. Qantas used Hawaii as a hub, where its various flights from the west coast of North America set down and passengers redistributed for various Australian destinations. Not very common any more, when the jets can hop from LA (for instance) all the way to Sydney. You might need to set up a multi-destination itinerary specifying Hawaii to make it happen.