"What happened to those other underpants you had?" -- Flight of the Conchords
Stefan - you can get styrofoam containers at lots of shipping places (not sure about in HI, but in general) . These are basically what I'd use: http://www.uline.com/BL_5450/Styrofoam-Wine-Shippers
Shipping a bottle here and there as a gift (which of course, nobody should ever do ) these kinds of things do a good job at both helping protect the wine from the crazy temp variations on a plane...and breakage. To be extra careful, I'd also seal up the wine in a plastic bag before putting it into the styrofoam...just in case it breaks.