Spécialisé dans la piste, il a remporté quatre médailles aux Jeux du Commonwealth de 1974 et de 1978, a été champion du monde de la course aux points en 1980 chez les amateurs et est monté quatre fois sur le podium de cette discipline aux championnats du monde professionnels. Il a également connu plusieurs succès sur route, dont le Herald Sun Tour en 1984. Il a participé aux Jeux olympiques d'été de 1976 et de 1980.
Son frère Shane Sutton a été coureur à la même époque. Ensemble, ils ont remporté la médaillé d'or de la poursuite par équipes aux Jeux du Commonwealth de 1978 et les Six jours de Melbourne. Gary Sutton est également le père de Christopher Sutton, coureur professionnel de 2006 à 2015.
Lors des Jeux olympiques d'été de 2008 à Pékin, il est associé à Hugh Porter en tant que commentateurs sur la BBC pour les épreuves cyclistes.
Après avoir pris sa retraite de la compétition, Sutton est devenu entraîneur, passant 26 ans en tant qu'entraîneur national au sein de la Fédération australienne. En mai 2017, il est annoncé que son contrat au poste d'entraîneur de l'endurance féminine n'est pas renouvelé[1]. En août de la même année, USA Cycling annonce que Sutton est recruté comme entraîneur en chef sur piste de l'endurance[2]. Il décroche deux titres lors des Jeux olympiques de Paris en août 2024, avec la poursuite par équipes féminine et Jennifer Valente sur l'omnium. Il quitte son poste en octobre 2024, à 69 ans et retourne vivre en Australie.