What Happened to the Rings and Who Held Them?

For a brief time, all the Rings of Powers were presumably worn and used in Eregion between the time Sauron left the Elves after the rings were made (1590 SA) and when Sauron forged the One Ring (1600 SA). But as soon as Sauron put on the One Ring, the Elves took off all their rings for they finally saw through the deceptions of Sauron and realized that their creations would only be corrupted and used for evil:

"But the Elves were not so lightly to be caught. As soon as Sauron set the One Ring upon his finger they were aware of him; and they knew him, and perceived that he would be master of them, and of all that they wrought. Then in anger and fear they took off their rings."
[The Silmarillion].

Some counselled that their rings be destroyed but the Elves could not bring themselves to destroy the Rings -- and so they were hid. The Seven and the Nine were separated. Of the Three, Celebrimbor gave one, Nenya, to Galadriel, and the other two, Vilya and Narya, to Gil-galad. In turn, Gil-galad kept Vilya and gave Narya to Cirdan of the Grey Havens to hold. An alternate to this version states that during the first Council of the Second Age, it was deemed wise that Elrond receive the ring Vilya and Gil-galad kept Narya until departing to war in the Last Alliance.

Angered that his plan was revealed and failed, Sauron made war on the Elves to claim the Rings without his help they could not have made. He laid Eregion to waste and sacked the Elvish city of Ost-in-edhil. He then captured and tortured Celebrimbor into revealing where the Rings were hidden:

"There Sauron took the Nine Rings and other lesser works of the Mirdain; but the Seven and the Three he could not find. Then Celebrimbor was put to torment, and Sauron learned from him where the Seven were bestowed. This Celebrimbor revealed, because neither the Seven nor the Nine did he value as he valued the Three: the Seven and the Nine were made with Sauron's aid, whereas the Three were made by Celebrimbor alone, with a different power and purpose."
[Unfinished Tales]

Using Celebrimbor's body as a battle standard on a pole, Sauron returned with war and overran all of Eriador in search for the Three Elven Rings. But he never found them and only suspected where they were hid. With the help of the Numenoreans, Sauron was finally driven out of Eriador c. 1701 Second Age and there was peace for a long while.

Sauron's power was later challenged by the Numenoreans and he was taken back as prisoner where through the use of the One Ring he corrupted them and incited them to rebel against the Valar. Then Iluvatar was called on and the world was changed and Numenor drowned in the ocean. Sauron went down as well, but his spirit fled (with the Ring) back to Middle-earth. When he took shape again he saw how the Numenoreans had grown in strength where their new kingdoms sprang up. He resolved to make war and drive them out before they became too strong. Then the Last Alliance was formed between Elves and Men to battle Sauron. There, before the Black Tower, Barad-dur, Sauron was thrown down and vanquished in the year 3441 Second Age.

But after a respite, Sauron's spirit appeared again in the Third Age and threatened the free people in Middle-earth. Around the year 1000 Third Age the Istari, or Wizards, came to Middle-earth to help in the struggle against Sauron. Last to come was Gandalf and Cirdan was moved to give Narya to Gandalf as he saw that it would be put to better use:

"Take now this Ring, he said; for thy labours and thy cares will be heavy, but in all it will support thee and defend thee from weariness. For this is the Ring of Fire, and herewith, maybe, thous shalt rekindle hearts to the valour of old in a world that grows chill."
[The Silmarillion]

So at the time of the story of Lord of the Rings, the Three Elven Rings were in the hands of the Wise; Gandalf, Elrond, and Galadriel, the Nine Sauron held, as well as four of the Seven (the other three were consumed by dragons), and the One was in the hands of Frodo the Hobbit.