Appearances of fur balls with and without trouble, by Jörg Hillebrand and Bernd Schneider
TOS: "The Trouble with Tribbles" and DS9: "Trials and Tribble-ations", built around the TOS classic, are clearly the most prominent episodes with Tribble appearances. But the furry lifeforms are shown or mentioned several more times in Star Trek.
Appearances of Tribbles
TOS: The Trouble with Tribbles
TOS: "The Trouble with Tribbles", set in 2268. At this time the species is fairly unknown in the Federation. At least Uhura has never seen one before when trader Cyrano Jones offers a Tribble for sale. No one of the Enterprise crew knows how to deal with their fast asexual reproduction that soon floods the ship with fur balls. Actually, the single original Tribble brought to the station Deep Space K-7 multiplies to 1,771,561 according to Spock's math. The figure is based on the assumption that each Tribble creates 10 offsprings every 12 hours. Including the already existing Tribbles the total count at any time translates to powers of 11. After 72 hours of reproduction we have six generations and hence 11^6 = 1,771,561 Tribbles.
It is the Tribbles that foil the plan of Arne Darvin, a Klingon in human disguise who has poisoned the shipment of quadrotritricale on Deep Space K-7, a grain intended for the colonization of Sherman's Planet. The Tribbles die in large numbers after consuming the poisoned grain, and it is also the Tribbles who blow the whistle on Arne Darvin's true identity, because while they purr pleasantly in the presence of other humanoid species, they react with hostile squeaking to Klingons. In the end, Scotty beams the Tribbles on the Enterprise over to the Klingon ship as a special "courtesy".
Star Trek III
Tribbles appear in the bar in "Star Trek III: The Search for Spock" in 2285, when Dr. McCoy, under the influence of Spock's katra, attempts to hire a transport to the Genesis planet. It remains unknown how these Tribbles, if they are really Tribbles, can be kept from reproducing rapidly. Since the people in the bar are delighted to stroke them exactly like in the classic TOS episode, they are definitely meant to be Tribbles.
TNG: When the Bough Breaks
DS9: A Man Alone / The Nagus
Visual TOS References in Modern Star Trek.
Side note The panel in Keiko's class room shows three other known alien species. The creature on the upper left is the true appearance of Korob and Sylvia as seen at the end of TOS: "Catspaw". The middle-left images in the bottom row depict a Regulan bloodworm, the ones on the right in the bottom row a Denebian slime devil. Both depictions are originally from the non-canon Starfleet Medical Reference Manual.
Star Trek Generations
Also in "Generations", a Tribble graphic can be seen in a lab on the Enterprise-D. It is a part of the display that already appeared in Keiko's class room.
DS9: Trials and Tribble-ations
In addition, we learn that, by the end of the 23rd century, the Klingons had eradicated the Tribbles on their homeworld. The squeaking furry creatures were regarded by his people as an "ecological menace", as Worf puts it. Bashir and O'Brien witness how the Tribbles take over the Enterprise in 2268, something that they would recall in DS9: "What You Leave Behind".
ENT: The Breach
TAS: More Troubles, More Tribbles
We learn a lot about the Tribbles in TAS: "More Troubles, More Tribbles". They seem to grow to a huge size after Cyrano Jones has tried to genetically halt their fast breeding. But the huge Tribbles are actually colonies that Dr. McCoy breaks down with a dose of neoethylene, with the success that these Tribbles procreate at a much slower rate. The Klingons, on the other hand, have bred a predator called glommer to hunt the Tribbles. The glommer was unable to deal with the giant Tribbles, however.
On a special note, the Tribbles in the TAS episode are all pink. It was unknown at the time that director Hal Sutherland was color-blind, and so he didn't notice their odd color.
Star Trek (2009)
A Tribble appears in a cage on Scotty's desk on Delta Vega in "Star Trek (2009)".
Star Trek Into Darkness
Dr. McCoy injects Khan's blood into dead Tribble, which brings the creature back to life.