The Labyrinth is an underground complex in New York, part of an abandoned portion of the city's subway tunnels.
When the gargoyles first awakened in Manhattan, the Labyrinth was being used by Cyberbiotics as a research facility; Hudson and Bronx raided it to obtain one of the three disks that Xanatos had the clan steal for him. ("Awakening Part Five") Not long after the raid, the complex also suffered a fire and was eventually abandoned (and after the destruction of Fortress-1, Cyberbiotics could no longer afford a hidden underground facility). 
More than a year later, Goliath brought Sevarius to the abandoned facility after kidnapping the scientist, and put him to work to find a cure for the Mutates' condition. ("The Cage") Following this adventure, the Mutates settled in the Labyrinth, and made it their home.
Homeless people throughout the city came to settle there as well, under the Mutates' protection. While Talon was their nominal leader, he was slow to take on this position, and Fang took advantage of the leadership vacuum in an attempt to take over the Labyrinth and rule it as a tyrant. Talon finally defeated him, however, with the aid of Hudson and the Trio, and recognized the need to serve as its leader. He decreed that the community now formed in the Labyrinth would be ruled by justice rather than by force, and forbade all weapons there. ("Kingdom")
The gargoyles brought Demona to the Labyrinth for imprisonment after their capture of her at the Goldencup Bakery Building. Her imprisonment did not last long, however, for she was rescued by Thailog not long afterwards. After the defeat of the two villainous gargoyles at Coney Island Amusement Park, the Clones joined the Labyrinth's community, where Talon would teach them to think for themselves, and to use verbs. ("The Reckoning")
On Halloween 1996, Goliath and Brooklyn visited the Labyrinth in order to check on the Mutates and the Clones, and Goliath asked Delilah on a date at Elisa's insistence. Shortly thereafter, the facility was raided by Thailog, who left with the Clones in order to wreak havoc at the Eyrie Building and collect DNA samples from the Manhattan Clan. Later that night, Delilah, Hollywood, Burbank and Malibu returned to the Labyrinth on their own volition. To many, this marks the true beginnings of the Labyrinth Clan. ("Invitation Only", "Masque", "Bash")
Real World Background
A labyrinth is a winding path, incised or painted on the floor, used in churches since at least medieval times. Often the act of walking a labyrinth is used as a ritual substitution for pilgrimage, or as a form of walking mediation.
In Greek mythology, the Labyrinth was a complex maze in the island of Crete. King Minos imprisoned the Minotaur within this maze, where he was killed by Theseus. The Labyrinth was constructed by Daedalus, who also built Talos.