Gary is a rather ordinary Goomba and a member of King Bowser Koopa's legion of minions, the Koopa Troop.
In Super Paper Mario, Gary and an unnamed companion of his, also a Goomba, were amoung the minions of Bowser to be transported to his wedding to Princess Peach and later, Count Bleck's castle.
After wandering around aimlessly in Count Bleck's castle, Castle Bleck, Gary and his Goomba companion found an unconscious Luigi who they, after complimenting him and telling him how great he was, used as a bodyguard. After travelling with Luigi for sometime and whispering snide remarks about him under their breathe, Gary and his Goomba friend came upon a dead-end in Count Bleck's castle.
Before either Luigi, Gary or the other Goomba could turn back though, Gary was zapped by Nastasia's, Count Bleck's assistant, hypnotic powers and transformed into a mindless servant of Count Bleck. Gary was last seen attacking Luigi along with his Goomba companion, who, at the sight of Gary being brainwashed, willingly joined Count Bleck's side.