The Cave of Terror is a natural cave formation near the spawn point of our heroes' Minecraft world. It first appeared in Minecraft - Part 1: How to Survive the First Night. Honeydew and Xephos choose this as the location to construct their Nether portal.
When it was first seen, Xephos pointed out a 'hopping green thing', causing Honeydew to sprint backwards and exclaim "Oh, Christ almighty! It's a creeper!" Xephos then began to walk towards the creeper, only to be quickly stopped by Honeydew. Later, in Minecraft - Part 6: The Mysterious Tree, the two explore the cave, only to discover there's nothing in there, not even the creeper they saw earlier.
In Minecraft - Part 16: Dark Constructions it became home to Honeydew and Xephos' Hellgate (later destroyed at the start of Season 3 in Minecraft - "Shadow of Israphel" Part 1: Crash and Burn) and also got connected to The YogCave via a tunnel that Honeydew and Xephos dug in Minecraft - Part 19: Tunnelling in the Dark (Multiplayer Survival). This was near where The Celaeno crashed in Season 3, and had changed slightly: Sand was coating the floor near the Gate. Originally, our heroes had planed to chase Israphel through the Gate, but he had sealed it behind him. They then took out the Gate at Old Peculier's request, and used the tunnel to escape to The YogCave, or what was left of it.
It should also be noted that an absurdly extensive tunnel connects the cave to Israphel's underground castle, implying that the Gate has a great significance to Israphel's sudden acquisition of power over Minecraftia.