Trivia: McCoy's statement "Spock, you really HAVE gone where no man has gone before!" is the first time that the TV show's title catchphrase was used in-universe. Since this movie other productions such as "Star Trek V" and "Star Trek - Enterprise" have established the phrase as Starfleet's motto.
Trivia: The scene in which Chekov and Uhura beam onto the Enterprise aircraft carrier was originally slightly different. It was scripted that they would sneak onto the ship undetected, but the American Navy believed that it would be impossible for two intruders to get past a military security force. So it was re-written that the transporter had enough energy to beam the pair onto the carrier, but not to get them back off.
Trivia: On the original VHS and Paramount Widescreen DVD releases, the synopsis on the covers says this, "A thrilling, action packed mission for the Starship Enterprise". As anyone who knows their Star Trek, this was the one movie that didn't feature the Enterprise in any capacity except as a flashback at the start and a brief reprisal at the end, the Klingon Bird of Prey was the ship they had the adventure in.
Trivia: Eddie Murphy was originally planned to take the role of the 20th Century Terran who assists the Enterprise crew in their efforts to retrieve the Whales. He would have played an English teaching college professor who believes in extra-terrestrials and witnesses the Enterprise crew's arrival when they materialise above a football game being watched by Murphy. While everyone else believed it to be a special effect for the game, Murphy would believe it was E.T.s arriving on Earth. This plan was eventually abandoned when the studio realised that they could make more money by keeping the two franchises separate and making a Trek film and a Murphy film. In the completed film, Murphy's character was changed to a female marine biologist and played by Catherine Hicks (although many of the scenes written for Murphy's character were used, if slightly altered).
Trivia: The scene in which Chekov and Uhura ask people on the street where Alameda is was basically unscripted. Most of the people, except a few who were hired to react, were actual pedestrians, and the policeman was hired only to be bodyguard to the actors. Leonard Nimoy only gave Walter Koenig directions to repeat "nuclear wessels" load and clear, and then sat back with the camera in a 'Candid Camera' type manner.
Trivia: The Cetacean Institute is really the Monterey Bay Aquarium in Monterey Bay, California; the Institute's logo also belongs to the Aquarium