The episode's title is derived from Iron Butterfly's 1968 song In-A-Gadda-Da-Vida, which was also lampooned by Matt Groening's other animated creation The Simpsons in the seventh season episode Bart Sells His Soul. Interestingly, in that episode Bart changes the song's title to In The Garden of Eden, which was also the original title of the song and one of the main settings of this Futurama episode (at least apparently).
This episode makes many Christian biblical references, including the following:
Leela and Zapp apparently land in the original Garden of Eden.
The Tree of Knowledge is shown, even including a talking serpent (according to Zapp, a product of their dehydrated minds) trying to make her eat apples from the Tree.
Leela eventually eats an apple from the tree.
The title references the famous Garden of Eden, the supposed paradise homeland of mankind, which is still sought after by many biblical explorers.
The V-GINY probe is a reference to V'ger from Star Trek:The Motion Picture. It is also a play on words on "vagina".
When Hermes is looking for matches to V-GINY he says "it's not on the Janeway's guide either" this may be a reference to Star Trek: Voyager's Captain Kathryn Janeway, and Star Trek enterprise's temporal cold war story arc, in which a mechanism is found that holds holographic blueprints of many different ships. (The Star Trek device was probably alluding to Jane's guides, which are annually published military vehicle and weapon identification guides.) She is also mentioned in the episode: When Aliens Attack. In that episode Fry says he wants to be a Sci-Fi hero like Captain Janeway.
The death sphere is a reference to the death star from the star wars trilogy.
In the episode bender mentions a "happy meal toy" a references to the McDonald's Corp.