OK, here we go...
The regulations differ depending on the makup of the crew. Some airlines have additional restrictions in the pilot's contracts, but this is the strict FAA interpetation.
For a three man crew (two pilots and one additonal flight crewman) such as on the DC-10, you can fly up to 12 hours in any 24 consecutive hours (moving window). Therefore, just about any flight to Hawaii from the east coast of the US can be flown by a basic 3 man crew without violating the rest requirements. And, after the normal 24 hour layover in the islands, they're ready to make the return trip home.
For a two man crew however (i.e. 767), they're only allowed 8 hours flight time in any 24. Therefore, if the flight is scheduled for more than 8 hours, they'll put on a third pilot, sometimes called a cruise pilot, to put them back into the three man rule above. The third pilot may ride in the cockpit jumpseat, or have a seat reserved for him in the cabin. That all depends again on the particular contract with the airline.
There are ways around the 8 hour rule, but it requires a rest period in the middle of the 8 hours equal to double the flight time up to that point. For instance: A two pilot 767 flight from Honolulu to the west coast leaves HNL in the late afternoon, arriving in the evening. The next morning they get up and fly back to HNL. They get back 24 hours after they left. Total flight time is 11 hours, and all within 24 hours. How did they do that? By putting rest in the middle of the flight time equal to double the flight time before the rest. So if they flew five and a half hours to the west coast, they'd need 11 hours rest before they left to return to HNL. This can rapidly turn into a scheduling nightmare if there are delays on departure from HNL. Is it cheaper to put a third man on a two pilot airplane? Or should the airline layover the pilots a day and a half on the west coast. That is a question best left to the accountants and the pilots union.
In the end, the reason the airlines mentioned in the original post gave up longer trips to HNL probably has more to do with economics of post-9/11 than crew rest requirements.
Hope this helps.
One smooth landing is skill. Two in a row is luck. Three in a row and someone is lying.