Australiano, nato il 4 settembre 1966 a Melbourne, Gary è figlio di Ron, professionista dal 1960 al 1967.
Gary è stato tra i migliori sprinter australiani e non solo, nell'arco di quindici anni. Nel 1986 ha vinto la prova sprint ai Giochi del Commonwealth, battendo il canadese (figlio di italiani) Alex Ongaro. Rivince i giochi anche nel '90 e nel '94, precedendo in entrambe il monumentale canadese Curt Harnett. Alle Olimpiadi del 1988 a Seoul, Neiwand ottiene la medaglia di bronzo, dietro al fuoriclasse tedesco dell'est Hesslich, e al sovietico Nicolay Kovche.
Nel 1991 ai mondiali di Stoccarda, ottiene il terzo posto, battendo nella finalina Harnett. L'anno seguente ci sono le Olimpiadi a Barcellona, e l'australiano conquista la medaglia d'argento dietro al tedesco Fiedler.
Alla fine del '92 Neiwand attua il grande cambiamento. Passa professionista e si trasferisce in Germania, e precisamente a casa dell'amico Michael Hubner, che in quegli anni è il mattatore delle specialità veloci nei professionisti.
Il programma di allenamento seguito assieme a Hubner, gli fa ottenere notevoli miglioramenti, tanto che, nei mondiali 1993, svoltisi in Norvegia, a Hamar, Gary fa siglare il miglior tempo nelle qualificazioni, con 10"19, ed arriva senza problemi in finale, dove incontra niente meno che il suo grande amico, Hubner.
La prima manche la vince Neiwand, e Hubner pareggia il conto vincendo la seconda, dove parte in testa con Neiwand che non riesce a completare di un soffio la rimonta.
Nella terza e decisiva prova, il colosso tedesco usa la stessa tattica della seconda manche, partendo in testa, ma stavolta Neiwand riesce, con il colpo di reni, a sopravanzare Hubner, conquistando così, il primo mondiale open della velocità. Quel che succede dopo la finale ha poco di edificante, per tutti e due i protagonisti. Infatti Neiwand dice ai giornalisti che Hubner ha tentato di corromperlo, promettendogli ingenti somme di denaro nel caso gli avesse lasciato la vittoria. Da quel momento finisce l'amicizia dei due, che oltre ad ignorarsi reciprocamente, vengono più volte quasi alle mani, come in occasione dei mondiali 1995, durante i quarti di finale nella velocità.
Nel mondiale '93, Neiwand si aggiudica anche il titolo nel keirin, dopo la squalifica del primo classificato, il francese Magne.
Le stagioni seguenti non sono ricche di soddisfazioni per Neiwand, che nel 1994, dopo i Giochi del Commonwealth, si fa male e l'infortunio non gli consente di competere al meglio ai mondiali di Palermo.
Nel 1995 si piazza quarto nella velocità, e nel 1996 dopo il secondo posto nella prova di coppa del mondo a Busto Garolfo (alle porte di Milano), vinta da Curtis Harnett, si presenta in grande condizione alle Olimpiadi di Atlanta.
Nelle qualificazioni dei 200 metri lanciati realizza subito il miglior tempo con 10"129, record olimpico.
Il cammino di Neiwand nel torneo procede con autorevolezza sino alla semifinale, dove un rinato Jens Fiedler frantuma i suoi sogni di gloria. Nella finale per il terzo e quarto posto se la vede contro Harnett, rivale di tante battaglie alla sua ultima gara, e vince il canadese due a zero.
Dopo un mese Neiwand conquista il secondo posto nel keirin ai mondiali di Manchester, e vince, assieme a Hill e Kelly il titolo nella velocità a squadre (allora chiamata anche "velocità olimpica").
Nei mondiali del 1997, una caduta nella semifinale del keirin lo mette fuori gioco, e successivamente non si presenta nelle edizioni 1998 e 1999.
Si ripresenta invece in gran spolvero nel 2000, alle Olimpiadi di Sidney, nella sua Australia, dove si conquista il bronzo nella velocità a squadre (assieme a Sean Eadie e a Darryn Hill), ed l'argento nel keirin, battuto per un soffio dal francese Rousseau in una splendida volata. Subito dopo pone fine alla sua carriera agonistica.