The "All employeez must haz cat to enter!!!" poster is a reference to the popular internet trend known as lolcats, in which pictures of cats are shown along with misspelled captions.
When Amy is measuring the lava temperature in the beginning scene, she says the "Magma P.I. Is x Degrees Selleck" Magma P.I. Is a Reference to the Show Magnum P.I. starring Tom Selleck.
The cat sings the "Meow-Mix Song" in order to bring the flying saucer to the Planet Express building. When the saucer responds, the window glass breaks. This is a reference to the 1977 film Close Encounters Of The Third Kind when the alien mothership responds to music being played.
The episode name is likely a reference to the 1965 Disney movie, That Darn Cat.
Nibbler says they can call the play "Nibbler On The Roof" which is a reference to a earlier episode called "Teenage Mutant Leela's Hurdles' where Leela and Fry race past a theatre with a play playing called "Fiddler Way Way Over The Roof".
When the Head Cat shares their history and how they were revered in Egypt of ancient Earth, he speaks of "feasts most fancy" and "vittles most tender", the cat food brands Fancy Feast and Tender Vittles.