The devices were first introduced and used by the Romulans in the original series episode "Balance of Terror". The invisibility came as a surprise to the crew of the Enterprise, who considered it only a theoretical possibility. In a later episode, the Enterprise is sent on a mission to try and capture one of the devices.
It was next seen in Star Trek: The Motion Picture, being used by Klingons. To explain this, fans have speculated that as part of an earlier mentioned Romulan-Klingon alliance, the cloaking device was given to the Klingons in return for the warp drive. Critics of this theory point out that it requires the Romulans to have fought an interstellar war without faster than light drive. The Enterprise episode Minefield shows cloak-using Romulans far away from home. Certainly the alliance existed, and Romulans were seen using Klingon ships, as stated in The Enterprise Incident.
Cloaking is not perfect. In "Balance of Terror", the Enterprise was still able to detect the Romulan ship on motion sensors, and in the Star Trek: Deep Space Nine episode "The Search" we learn that running at a high warp speed may allow detection. A major plot element of Star Trek: The Undiscovered Country was the invention of a new type of cloaking device that would allow firing whilst cloaked. In the Star Trek: The Next Generation]] episode "Redemption", the Federation discovers a way to use nets of tachyon beams to set traps for cloaking ships. As detection methods advance, so too do cloaking devices.
Many have wondered that after Kirk captured a cloaking device, why the Federation have not used them on their ships. Gene Roddenberry claimed that this is because Starfleet are scientists and not sneaks - but this was addressed in "The Pegasus", which claims that the Federation is bound by a treaty with the Romulans not to develop them. This treaty is known as the Treaty of Algeron.
[note: Star Wars has references to Cloaking devices; to be written]