To gain entrance, speak with Rottytops in her caravan marked 'Keep Out' at the Zombie Caravan, and beat her at her race (see the FAQ for advice on how to do this), then meet her at the labyrinth entrance afterwards.
It is inhabited by and endless supply of Cacklers (skeletons who rise from the ground), Shriekers (tall birdlike specters who summon ghosts), and Succubi (vampiric she-demons with heart-shaped tails). In spite of the numerous spiderwebs, there are no spiders to speak of. There are also a lot of spikes and moving eyeball platforms. The principle puzzles of this labyrinth involve placing eyes into the sockets of statues to reveal keys. Typically this will require multiple tries as the eyes need to be facing a nearby object that will elicit a reaction from the statue.
Transform into a spider and walk around on the grids above, pressing down the buttons as you pass over them. These buttons open up trapdoors in the floor that will cause the giant to plummet and take damage if he is standing over these trapdoors.
Remaining in these grids will largely protect you from contact with this creature anyway.
It's also possible to inflict damage directly with Shantae's hair attacks, but the spider method is far easier.
In the first room with the eyeball platforms and spikes, ride the eyeball to the right until you pass under an overhang and arrive at another eyeball similarly placed under the floor like the first one. There is an eyeball platform above that can be reached with the monkey - ride it upwards to find a baby warp squid.
There is a long corridor with a spiked ceiling and a floor full of spike traps. At one point you are expected to ride an eye platform up to reach another area - but if you stay aboard, you'll pass through the ceiling and find a warp squid waiting for you in a hidden chamber.
There's a room with an arrow pointing up. While it may be an insanely obvious clue, it's also easy to overlook. Jump up there with the Monkey (be careful to get exactly the right spot) and climb to find it.
There is a room made of slopes that will slide Shantae all the way to the bottom. Once you have Harpy form, fly upwards from the bottom to find an enclave across from the last slope with Baby Warp Squid.