California Doubling: Camp Khitomer is The House of the Book performance hall and library building at the American Jewish University, Brandeis-Bardin Campus in Simi Valley, California (best known as the Command Center/Power Chamber from Power Rangers). The foreground is the Fireman's Fund Building in Novato, Northern California.
This was at least partially a coincidence, as Brock had already played Admiral Cartwright earlier in the film series, Brock Peters plays an anti-Klingon racist. Brock actually had problems doing Cartwright's anti-Klingon rant during the classified meeting because it was morally unpleasant for him personally. Multiple takes had to be done and pieced together. (That is, he had problems getting the lines out. According to the DVD, he was supportive of the message itself.)
A bit of one with Christopher Plummer, a respected Shakespearian actor as the Shakespeare-quoting Chang.
Deleted Scene: Rene Auberjonois filmed a small role as a Starfleet member initially presented as being an ally to Kirk and Spock, only to be revealed as an aid to the conspirators. His scenes were cut for the theatrical release, reinstated for the VHS and DVD, only to be cut again on the Blu-Ray.
Gene Roddenberry. Again. He had a hard time with Saavik being the traitor. He won this battle, and a new character was created instead.
Klingon blood is pink for the first and only time in the entire Star Trek property because had it been red, the film would have been slapped with an R rating.
A Chekhov's Gun example is subverted slightly via Executive Meddling. At the film's start, we learn that the Excelsior has been cataloging gaseous anomalies... but in its Big Damn Heroes moment, it's the Enterprise that interestingly just had the same technology installed recently to create a gas-seeking torpedo to find Chang's ship.
Real-Life Relative: Walter Koenig's wife, Judith Levitt, is one of the Starfleet Admirals at the briefing towards the beginning of the movie.
Starfleet Admiral: Bill, are we talking about mothballing the Starfleet?
Recycled Script: Accidentally, as the writer didn't know there had been an episode of the series where Kirk fought a clone of himself. Though it does still work as twenty years of special effects advances allowed this fight to be much more convincing than the last one, which was mostly done through single shots of both Kirks.
Throw It In: General Chang was supposed to have hair, however, Christopher Plummer preferred his bald look, so General Chang became bald.
Harve Bennett, the man who co-wrote and produced every Star Trek film between Star Trek II and Star Trek V, originally pitched a completely different sixth movie entirely. This movie would have been a Prequel, featuring the characters of Kirk, Spock, Bones and Scotty; recast as younger actors and meeting each other for the first timeat Starfleet academy. This may all sound very familiar with the benefit of hindsight. The story would have been about Cadet Kirk's one true love, and her death — the thing which drives him towards adventure, and which never allowed him to settle down and have a family. The movie would have featured cameos from William Shatner and Leonard Nimoy at the start and end of the film, where they visit the grave site of the girl that Captain Kirk has never allowed himself to ever forget. An alternate framing device would've had DeForest Kelley as McCoy telling students at "present-day" Starfleet Academy about how he'd met Kirk and Spock.
Bennett's story was seen as very risky in 1990 (recasting the roles of Captain Kirk and Mister Spock? Get outta town!), and was eventually shut down by Executive Meddling — the suits simply didn't feel that the movie going public at the time could ever accept such a radical departure. They pushed for Bennett to write a more traditional Star Trek, with all the original cast. Bennett refused to do this, and walked from the project. Nicholas Meyer, Denny Martin Flynn and Leonard Nimoy knocked together the eventual version in something of a hurry (they had to have the movie out in time for the 25th anniversary of the original series), so its probably quite surprising that the final movie turned out as well as it did.
Not just executive meddling. When told about the plan to recast, some of the original cast spread rumors at cons that it was going to be a farce along the lines of "the Jetsons crossed with Police Academy." Fans rioted and the plan was scrapped. Didn't help that Gene Roddenberry was against it as well.
As for making the film in a hurry for the anniversary, an Academy film would almost certainly have never made it out in time. A prequel would've required all-new sets, costumes, and models, while a film set on the Enterprise-A allowed them to reuse all of their existing assets, saving a lot of time and money.
Even the story they eventually went with could have been a lot deeper. In the novelization, the Klingons were responsible for a massacre on the Federation colony of Kudao (which the Klingon government claimed was a rogue action), and Chang's bird-of-prey attacked a science station on the planet Themis inside Federation space, which critically injured Kirk's love interest, Carol Marcus. Had they kept this in, it would have provided more recent context for why the Klingons were so mistrusted, and another personal reason why Kirk hates the Klingons so much— considering that David's death happened ten years or so before the events of Star Trek VI.
The original idea for the opening was to have Kirk and Spock round up the officers for their final mission. This would have shown their fates and why they were so eager to return. Scotty would be struggling to understand the cloaking device on the stolen Bird-of-Prey. Uhura would be hosting a talk radio show. Chekov would be playing chess with higher life forms, gloating about his "superior Russian strategies". McCoy would be surrounded by insufferable doctors. Kirk himself would be in bed with Dr. Carol Marcus. However, the budget would not allow for such a pricey sequence, so it was scrapped.
And if they'd gone with Saavik as the one to betray Starfleet, and if the film versions of The Wrath of Khan and The Search for Spock had followed the novelizations by having Saavik and David fall in love, it would have provided an excellent personal reason for Saavik to wish the Klingons dead.
Given that Saavik was strongly implied to be Spock's lover (in ST:III), and pregnant with his child (in the novelization of ST:IV), it would have made her betrayal and extremely public Mind Rape by her husband much more distressing than the final script's version.
Walter Koenig also submitted a story idea he was rather proud of titled ''In Flanders Field'' that would have ended with the deaths of everyone except McCoy and Spock, both of whom had already been seen alive by the time The Next Generation took place ("Relics", featuring Scotty, aired a year later).
Homage: The speech that the warden gives Kirk and McCoy upon their entry to Rura Penthe is a paraphrase of Colonel Saito's speech to captured British P.O.W.s in The Bridge on the River Kwai. For comparison:
Colonel Saito: If you work hard, you will be treated well. But if you do not work hard, you will be punished! A word to you about escape. There is no barbed wire, no stockade, no watchtower. They are not necessary. We are an island in the jungle. Escape is impossible. You would die. Rura Penthe Warden: This is the gulag Rura Penthe. There is no stockade. No guard tower. No electronic frontier. Only a magnetic shield prevents beaming. Punishment means exile from prison, to the surface. On the surface, nothing can survive. Work well, and you will be treated well. Work badly, and you will die.
Recycled Set: This movie was filmed while Star Trek: The Next Generation was still in production. As a result several of the TV show's sets found their way into the movies. However, these sets were originally designed for the first Star Trek movie and late redressed for television. Some sets, such as corridors and crew quarters had a few different paint jobs and cosmetic touches, however, others were a bit more obvious:
Main engineering of the Enterprise-A was essentially the Enterprise-D's main engineering set with different graphics in the displays and a different paint job.
The officer's mess hall was the Enterprise-D's observation lounge set. This is why the little Enterprise statues that are present in that set during the first four seasons of the show mysteriously disappear.
The Federation President's office is the Enterprise-D's Ten Forward with some curtains and different lighting.
Kirk's quarters set was recycled for Data's in Star Trek: The Next Generation and then recycled back for this film. The added replicator set piece had its panel changed and used as an shelf. Data's quarters were, themselves, a redress of Kirk's Motion Picture and Wrath of Khan quarters — this is the TNG "junior officer's quarters" set and is used variously for the quarters of Data, LaForge, Chief O'Brien and Worf, before he had Alexander.
Ship Tease: Very subtly between Spock and Valeris, reflected in their UST-filled nightcap and his emotional response to her betrayal. This is likely a remnant of the original script which was to have the established character of Saavik instead of Valeris (reflecting the fact Spock and Saavik were strongly implied to have mated in Star Trek III and a deleted scene in Star Trek IV had established that Saavik was pregnant with Spock's child; in the Expanded Universe novels, Spock and Saavik eventually marry.)
Unintentional Period Piece: Or intentional, as this movie could only have been made in the midst of the end of the Cold War of 1990-91. Since Cold War allegories played a big part in the original series in the '60s, it's actually rather thematically fitting that the original cast's story should end here.