In Wraith: The Oblivion and Orpheus, the Labyrinth is the interface between Oblivion and the Underworld. As many things are in the Underworld, Oblivion is a concept and a physical entity - there is a physical location, the Well of the Void that comprises Oblivion - the Labyrinth is that area surrounding it.
Oblivion destroys meaning, coherency and self, and the area surrounding the Well of the Void reflects that. The Labyrinth is an incoherent maze, infinite in size, composed of the aggregate detritus of the living world - it is not an ordered maze, but instead the absence of order. One corridor in the labyrinth can be a childhood hospital, the next an inverted volcanic tunnel where gravity operates in reverse.
The Labyrinth has relatively little structure, and no map could make sense of it; what landmarks do exist are prone to movement. To Stygians, the most obvious landmark is the Veinous Stair, the long stairway that leads from Stygia to the labyrinth. In addition, there are various phenomena such as the tombs of ancient Malfeans, and the Amphiskiopoli of Spectres.
To Spectres, the Labyrinth is home. They can Slumber in its walls as if the entire structure was a Fetter, and they form their own societies. The Malfeans and Grandmother have both staked out territories within the Labyrinth, which they defend from any intruding Spectre as much as they would from a wraith or ghost. At some point that is impossible to determine by any human understanding, the Labyrinth actually becomes part of Grandmother herself; she can directly control the conditions within these tunnels.