Domestic inter-island service is provided by Air Rarotonga (http://www.airraro.com). Although you can book flights through Air New Zealand, it is usually cheaper to do so directly with Air Rarotonga. This has become much easier in the past few years, now that they offer online booking. Unless you're a member of Air New Zealand's "Airpoints Dollars" program, you won't receive any airline miles for Air Rarotonga -- and then only if you book through Air New Zealand, often at a higher price. Star Alliance mileage for Air Rarotonga is not available.
Most of the outer islands have only unpaved runways. However, landing won't be much rougher than that of a paved runway. If you've never landed on an unpaved runway before, it's nothing to be overly concerned about, and you've probably had a few rougher landings on a paved runway.
The intrepid traveler can visit all inhabited islands by inter island freighters, but these can be weeks apart or worse if you want to get the really remote islands. Details of services are published in local island newspapers.
There are no generally scheduled boat or ferry services between the inhabited islands.
There are two uninhabited islands - Takutea and Manuae. The only easy way for a visitor to get to Takutea is on the research vessel Bounty Bay operated by Rarotonga-based Pacific Expeditions, which has special permission to run occasional eco tours.