Among the parts of parade balloons used in creating the hot air balloon that returns to the surface is made from Underdog, Bart Simpson, Bullwinkle J. Moose and Garfield's owner Jon Arbuckle.
Professor Farnsworth says that deciphering the alien language on Leela's note could take an hour or a hundred million years. This is a reference to the halting problem in computability theory.
Among the buildings Leela passes while running through the sewers is a Starbucks.
The wall upon which Leela's parents have chronicled her life is a reference to Being John Malkovich.
When Leela comes across the wall with her chronicled life, she gasps "Great Cheech's ghost!", which is a reference to the Superman character Perry White, who often says "Great Caesar's ghost!" when angry, exasperated or surprised. A similar reference was also made in Bender Should Not Be Allowed on TV.
Leela says "Or some kind of even more boring Truman Show?" when she asks the hooded figures about the Time line of her life. The Truman show is a film about a guy who was on live television watched by many all over the world.
The computer on the Warden's desk appears similar to the personal computers used in Star Trek: The Next Generation.
The idea for the character Leela and her back story were conceived of by Matt Groening and David X. Cohen before they even pitched the series to FOX. Because they knew from the beginning that Leela would later be revealed to not be an alien, they intentionally included a shot of Leela's parents in the previous episode I Second That Emotion.
As the plot for this episode developed though realized that the design of the characters needed to change to look less normal. In the original design, Morris had a normal mouth; and Munda had normal human arms, one of which was visible in her original appearance. For a while the idea was thrown around to stay true to some aspects of this design and Munda had a normal human arm and a tentacle arm. Eventually it was decided to make both arms tentacles and work under the assumption that in the previous appearance she had been wearing something similar to a human flesh colored glove.
There was a large amount of debate amongst the writers as to whether the truth of Leela's origin should be revealed to the viewer before Leela realized it or if it should be a surprise for the viewers as well. The final decision was made based on the idea that it would be easier to make jokes if the viewer were in on the plot.
The song playing during the scenes of Leela's childhood is "Baby Love Child" by Pizzicato 5.