A Gemstone Cave can be found underground within the cavern layer.
They contain a high concentration of gems around the edges of the cave, with a special back wall covered in the same type of gem (which can be removed with a hammer, but cannot be collected).
Any type of gemstone can be found in these caves, and they will sometimes contain two different gemstones (Example: Amethyst and Topaz, Ruby and Sapphire, etc.), and very rarely one can spawn with three or more different types of gemstone. Spelunker Potions are extremely useful while searching for these caves as they are rare and easy to overlook.