The tribbles apparently derive from the Martian "flat cats" of Robert Heinlein's juvenile novel The Rolling Stones. Twins Castor and Pollux transport a cargo of flat cats in cold sleep to miners in the asteroid belt. Both tribbles and flat cats are born pregnant.
Klingons are unique among Star Trek's races in their extreme hatred of these cute little creatures. This might be due to the fact that tribbles emit a loud shrieking noise in their presence (although the tribbles may just be reacting to the sight of their enemy).
Tribbles were originally encountered in the original Star Trek television series, in an episode titled "The Trouble with Tribbles." Captain Kirk and his crew encounter the Tribbles on a space station while arranging to transport some grain to a colony. The "trouble" with Tribbles is that they reproduce far too quickly - in the words of Dr McCoy, "They are born pregnant" - and threaten to clog up essential ship systems.
In Deep Space Nine episode "Trials and Tribble-ations" the crew of the USS Defiant[?] encounter the Tribbles once more. Since Worf reveals that the creatures were actually hunted down and exterminated by his people, this can only be achieved by time travel. Fortunately, or perhaps unfortunately depending on one's perspective, a number of tribbles were brought back to Deep Space 9 from the past and the species is reestablished. It is not known if this was deliberate or not.