George and Gracie were a pair of Humpback whales that wandered into San Francisco Bay as calves, and were brought to the Cetacean Institute in Sausalito. By 1986, they had become fully grown, each weighing 45,000 pounds. However, that year it was decided that they had to be released back into the wild because the Institute no longer had the money to feed them their two-ton requirement of shrimp per day.
George and Gracie came to the attention and interest of Admiral Kirk who had time traveled to 1986 in search for such a pair. In the 23rd century the powerful signal from a deep space probe has caused disruption of Earth's weather patterns, threatening the entire planet. An alien species had sent the probe to Earth to determine why they lost contact with humpback whales (which had become extinct in the 21st Century).
Upon visiting the Institute, Kirk and Spock determined that they were ideal specimens for their mission. Spock mind melded with the whales to communicate their intentions to taking them back to the 23rd century, wanting to avoid making the same kind of arrogant assumption that those who had hunted the whales to extinction originally had made. He would, in turn, learn that the whales were unhappy with the way their species have been treated by man, although they were apparently willing to help the time-travellers. He would also learn that Gracie was pregnant. Dr. Gillian Taylor notices this from a concerned visitor and is visually angry with Spock. After he and Kirk leaves, the whales comfort Gillian and convince her that Spock didn't mean any harm.
With the assistance of Dr. Gillian Taylor, Kirk and party were able to locate the whales after they were released; although they were targeted by whalers, the crew was able to beam them into a specially designed tank aboard their commandeered Klingon vessel.
After returning with Kirk to the 23rd century, George and Gracie were released into San Francisco Bay, amidst the chaotic weather caused by the Whale Probe. George communicated with the probe via the sounds made by the male of his species and the probe replied. Following a brief conversation, the probe ceased its disruptive signal and turned away from Earth, heading out into space.
The pair were last seen heading to open water. (Star Trek IV: The Voyage Home)