Most of the cruise lines already have this service. Last year I used it from Royal Caribbean's Rhapsody of the Seas. I only did text messaging, but they supported any GSM phone. I think the roaming rates were $5 a minute. It's called Cellular at Sea.

Sounds like it would be unfortunate to run out of prepaid minutes whilst at sea... Then again they would probably have web access and some method of recharging them online, I suppose.