As stated, generally the phones will not work at sea. However, it is hit or miss depending on the phone and the service provided. At certain points while at sea the ship will pass close enough to some land for some phones to work. You have to know exactly when to try it and then have the right phone and provider.
On our 8/25/04 cruise which was extended due to the hurricane, we sailed along the coast of Florida during the day on the return trip. You could see the coast (Miami, Ft. Lauderdale, etc) and many people could get service. Some however, included us with Verizon, could not get a call to go through even though we did receive a weak signal.
Our Verizon phones worked in all the ports on the Western cruise.