The cave is located at an undetermined location along the coast of Britain. The entrance can be found on a cliff that can only be reached by skilled mountaineers or with the aid of magic. To get inside, one has to swim through ice-cold sea water into a dark narrow tunnel which leads into a large cave that serves as the entrance hall to an even larger one that is filled by a lake with an island in the middle (HBP26).
Voldemort chose this desolated, gloomy place as the hiding spot for one of his Horcruxes, Salazar Slytherin's locket. This Horcrux was later stolen by Regulus Black and Kreacher, who left a fake copy which was found by Albus Dumbledore and Harry Potter sometime in June of 1997 (DH10, HBP26).
Tom Riddle found the cave on a vacation trip to the coast with the orphanage. He forced two other small children to come with him, probably to torture them. When Dumbledore went to collect Tom from his orphanage, the matron, Mrs. Cole, informed him that " well, Amy Benson and Dennis Bishop were never quite right afterwards, and all we ever got out of them was that they'd gone into a cave with Tom Riddle. He swore they'd just gone exploring, but something happened there, I'm sure of it" (HBP13).
Hiding the Horcrux
Years later, Voldemort chose to hide Slytherin's locket inside the cave. To protect it, he placed several protective spells upon the cave in order to prevent anyone from finding it. He sealed the passage from the entrance hall into the larger cave; an offering of blood must be given to open the wall. The lake was filled with Inferi and could only be crossed by a boat that held a single fully-qualified wizard. Voldemort placed the Horcrux inside a stone basin filled with a potion that causes pain and unquenchable thirst to the drinker. The Horcrux can only be removed when the potion is drunk. The only water available (as a simple charm to create water is somehow defunct in the cave) is to drink from the lake, thus awaking the Inferi (HBP26).
Regulus and Kreacher
To hide the Horcrux in the basin, Voldemort needed the assistance of somebody who could enter the boat with him, which ruled out qualified wizards. A year after Regulus Black joined the Death Eaters, Voldemort asked for the services of an elf. Regulus volunteered and offered Kreacher. He told the elf to go with the Dark Lord, obey his orders and return when the task was done. Voldemort took Kreacher with him to the cave, which he had chosen as the hiding place for Salazar Slytherin's locket. He wanted to use the elf - a worthless, disposable creature in his eyes - as a test for his defenses. Kreacher accompanied him into the cave and onto a boat that took them to an island in the middle of the lake. There, Voldemort let him drink the poison inside a basin he had placed there, threw in the locket, and refilled the basin. Voldemort then left, while the poisoned elf stayed behind. He had clearly intended Kreacher to die, but had underestimated the house-elf's power and dedication. Driven by the unquenchable thirst the poison caused, Kreacher drank from the lake and was dragged into the water by Inferi. However, before they could harm him, Kreacher Disapparated and returned to his master, as he had been told to do. Voldemort had overlooked that house-elves can Apparate at places where wizards cannot.
Kreacher told his master everything. Regulus became worried. He must have suspected what Voldemort had hidden in the cave. A short while later, Regulus asked Kreacher to take him to the cave. Kreacher knew how to enter the cave and get to the island. Regulus gave Kreacher a second locket and told him to switch the lockets once the basin was empty. He ordered the elf to return home alone, not to tell anybody what had happened and destroy the locket. Then he drank the poison and was dragged into the lake by Inferi. Kreacher watched his master die and returned home. However, he was unable to destroy the Horcrux, although he kept trying and punishing himself for his failure (DH10).
Harry and Dumbledore
Oblivious of the fact that Regulus and Kreacher had found the Horcrux before him, Dumbledore took Harry Potter to the cave. Dumbledore drank the potion and Harry fetched water for him from the lake, waking the Iferi. Dumbledore fought them with fire and they were able to get out of the cave and Disapparate. Only after Dumbledre's death did Harry discover that the locket they had found was not the Horcrux (HBP26).
Voldemort revisiting the cave
Voldemort believed that the cave was among the most impenetrable of his hiding places; he acknowledged, however, that Dumbledore might have found out details of his wayward childhood from Mrs. Cole. After Voldemort found out that Harry destroyed Hufflepuff's cup, he decided to visit and strengthen the hideouts of all the Horcruxes (DH27).
When Harry's quest led him to Hogwarts for the destruction of the penultimate Horcrux—Ravenclaw's diadem—, Alecto Carrow ran into him in the Ravenclaw common room. She summoned Voldemort to the school with the use of her Dark Mark shortly after he visited the Gaunt Shack and found that Marvolo's ring was gone. The Dark Lord chose to check the cave before going to Hogwarts, and was shocked to find that the locket was gone as well (DH30).