US Customs and Border Patrol does not require documentation, but they do have the right to delay your travel if they have a question as to whether you are taking a child out of the country without permission from the absent parent. Usually, this isn't an issue if you are cruising out of the US on either the Caribbean or Bahamas itineraries, but my opinion is it's better to be safe than sorry. If you have sole custody, you can bring your court documents. Otherwise, a signed and notarized letter from the absent parent works.
If you are traveling to Vancouver for an Alaskan cruise, you definitely need to have documentation. Canada is pretty strict about requiring it. I wouldn't travel to Europe without documentation either.