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
The Tribbles appear for the first time and most famously in 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
It is not entirely certain if the animal in this first-season TNG episode in 2364 is meant to be a Tribble. Anyway, Alexandra, one of the children later kidnapped by the Aldeans, takes a furry ball from a cage and kisses and strokes it at the beginning of the episode, which may be a sign that it is alive, rather than a stuffed animal. Her supposed Tribble has a braided strand of hair and something that looks like an eye. Later in the episode it gets stuck on Picard's uniform in the same fashion as the Tribbles in "The Trouble with Tribbles" whose adhesion even works on smooth walls.
DS9: A Man Alone / The Nagus
Tribbles can be seen on a display of "Comparative Xenobiology" in Keiko O'Brien's class room on Deep Space 9 in DS9: "A Man Alone" and once again in "The Nagus" (both in 2369). The graphic shows an exterior view and a cross-section that reveals some inner organs of the species. Also on this display, we learn that the scientific name of Tribbles is "Polygeminus grex" and that their home planet is Iota Geminorum IV. See also 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
The next appearance of the furry creatures is in "Star Trek Generations" (2371). Here a child is carrying one of the adorable creatures when the stardrive section has to be evacuated. It seems their fast reproduction is under control by this time and they are permissible as pets, otherwise the battle against trigger-happy Klingons and a mad scientist wouldn't remain the only problem in the movie...
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
The events of TOS: "The Trouble with Tribbles" naturally repeat in a very similar fashion in this DS9 episode. Using the Orb of Time that is being transported on the Defiant, Arne Darvin returns to K-7 in the 23rd century to take revenge on James Kirk, who exposed him as a Klingon spy with the help of the Tribbles. He puts a bomb into the storage compartment that Kirk would open. But Sisko and Dax find the bomb that is tied to a Tribble and have it beamed it into space. In spite of everything, the time travel does have consequences in the 24th century. After the return of the Defiant, Deep Space 9 is flooded with Tribbles much like K-7 in the 23rd century. It remains unknown how this infestation with fast-breeding 23rd century Tribbles can be removed until the following episode (2373).
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
The appearance of Tribbles that predates anything else on the timeline is in ENT: "The Breach", set in 2153. Here Dr. Phlox has brought some Tribbles aboard as food for his pets. He says "They're outlawed on most worlds." and "The problem is they breed quite prodigiously."
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. This will be the key to saving Kirk's life later in the movie.
DIS: "Context is for Kings"
In DIS: "Context is for Kings" we can see a Tribble on Captain Lorca's desk (and hear it purr). The Tribble remains on his desk for three later episodes.
A disastrous incident involving Tribbles occurs in SHO: "The Trouble with Edward". We learn that the previously harmless creatures are genetically manipulated by the eponymous Edward Larkin to breed rapidly. This is in direct contradiction to what Phlox said about them being fast breeding already 100 years earlier. The Tribbles destroy the USS Cabot, kill Larkin, then infest the planet Pragine 63 and head for Klingon space. This all happens a few years before the events of "The Trouble with Tribbles". The only explanation for the Tribbles not being immediately rated as a catastrophic disaster in the TOS episode is that Starfleet deleted all records and denied their existence.