Even though he wasn't presented in "Tonsil Trouble", he was allegedly working in the hotel off-screen and knew of the AIDS benefit events Eric Cartman did there as he revelead in "The Coon".
In "Ginger Kids", Cartman hosts a Ginger Pride rally at the Airport Hilton, after the boys make him believe that he is ginger. During the rally, Gary Nelson checks in on Cartman and does so again when Cartman prepares to kill the non-gingers. Focusing only on his job and not the subject of the meetings, he remains completely oblivious to what's going on.
He reappears in "The Coon" when Cartman, as The Coon, hosts a convention for himself, which no-one comes to. Gary checks in on Cartman, and questions whether The Coon is actually Cartman. Cartman, maintaining his alter-ego, ensures him otherwise, for which Gary replies, "I'm actually relieved. That kid was kind of a douchebag.".
Gary wears a black suit, consisting of black pants, a black coat, and a white shirt with a red tie. His coat is adorned with a brown nametag with his name. He has short, combed brown hair and no remarkable features.