To gain access, speak to Sky in her hatchery in Oasis Town, then meet Wrench at the labyrinth entrance afterwards.
True to its name, the labyrinth is inhabited by stone Golems. Additionally it is inhabited by a variety of magnetic creatures. Many of the labyrinth's puzzles related to manipulating these by charging Shantae with either red or blue polarity.
The boss - King Golem, a stone giant with a crystal brain - guards its treasure, the
You can see this one from the elevator, but you won't be able to reach it till later. Behind a locked door to the left of the elevator shaft is a room with a golem and four hanging lantern platforms. Use the monkey to scale up a shaft on the ceiling and then the elephant to smash through some stalagamajigs in an opening on the right.
In the chamber just above the shaft you scaled to reach the last warp squid, there are a bunch of blue lightning guys who rain bolts down on you. Go to the left and find the secret passage that leads you up to their level, and turn the tables on them. Once you've killed them all you'll find a baby warp squid to the right.
Close to the entrance, past the first set of stalageroonies you encountered on your way down, is a room where you fight one of those magnet men and acquire a key. The top left corner of this room has a hidden chamber with a warp squid inside.
In the room where you have to elephant charge a statue to get some stalagmites to fall into a pool of lava (all the way down the main elevator, then go through the left door), there is a BWS on a platform to the left and to the up of the lava pool in that room.
The main elevator shaft.
You'll need the Elephant to smash through those stalagmites and stalactites.