Fatti:
A. A._, cittadino italiano, e B._, cittadina austriaca, sono i genitori di C._ (nato il 26 luglio 1995) e D._ (nato il 28 gennaio 1997). Con sentenza 9 aprile 1999 il Tribunale distrettuale di Salisburgo ha sciolto per divorzio il matrimonio di A._ e B._, ha affidato i figli con l'esercizio esclusivo dell'autorità parentale alla madre, con un diritto di visita del padre.
B. B.a Nell'ottobre 2006, in seguito a problemi di salute della madre, i genitori si sono accordati nel senso che C._ sarebbe rimasto con il padre nel Cantone Ticino, dove ha frequentato la scuola media fino al marzo 2008, quando è rientrato a Salisburgo per trascorrere le vacanze di Pasqua dalla madre. Quest'ultima, trasferitasi con i figli a Gamlitz, non lo ha più lasciato tornare in Svizzera fino al 19 agosto 2008, pretendendone però il ritorno il 28 agosto successivo, richiesta a cui il padre si è opposto.
B.b Il 5 settembre 2008 l'Ufficio federale di giustizia austriaco si è rivolto all'omologo Ufficio svizzero chiedendo, sulla base della Convenzione dell'Aia del 25 ottobre 1980 sugli aspetti civili del rapimento internazionale di minori (RS 0.211.230.02; CArap), la riconsegna di C._ alla madre. L'Ufficio federale di giustizia svizzero ha incaricato l'avvocato Patrizia Casoni Delcò di intraprendere i passi necessari per il ritorno del minore. Tale legale ha sollecitato l'autorità di vigilanza sulle tutele del Cantone Ticino a ordinare il rientro immediato di C._ dalla madre. Dopo aver sentito i genitori e fatto ascoltare il minore da una psicologa, l'autorità di vigilanza ha con decisione 22 dicembre 2008 respinto la richiesta di rientro, perché C._ è risultato determinato e convinto a restare con il padre.
C. In accoglimento di un appello della madre la I Camera civile del Tribunale d'appello del Cantone Ticino ha, con sentenza 16 aprile 2009, ordinato a A._ di assicurare il rientro del figlio C._ presso la madre a Gamlitz entro il 31 maggio 2009. La Corte cantonale ha ritenuto che il mancato ritorno di C._ in Austria sia illecito, poiché il padre non ha alcun diritto di custodia, la dimora abituale del figlio si trovava in quel paese e che B._ esercitava effettivamente la custodia sul figlio, senza aver rinunciato a tal diritto. Con riferimento all'art. 13 cpv. 2 CArap, che permette di rifiutare di ordinare il ritorno in caso di opposizione del minore, i Giudici cantonali hanno ritenuto che C._ è stato messo sotto pressione da entrambi i genitori, che egli vive bene con il padre in Ticino e non vuole tornare dalla madre. Essi non hanno però ravvisato una consolidata opposizione del figlio ai sensi della giurisprudenza che giustifica un'eccezione al principio del rientro previsto dalla Convenzione.
D. D.a Con ricorso in materia civile del 30 aprile 2009 A._ chiede al Tribunale federale, previo conferimento dell'effetto sospensivo, di annullare la sentenza di appello e di confermare quella dell'autorità di vigilanza che ha respinto la domanda dell'ex moglie tendente ad ottenere il ritorno del figlio C._. Il ricorrente postula pure di essere messo al beneficio dell'assistenza giudiziaria. Egli ritiene inapplicabile la CArap, perché C._ sarebbe rimasto "su esplicita indicazione" della madre in Ticino dall'ottobre 2006 al marzo 2008, fino a quando quest'ultima ha fatto tornare il figlio in Austria con uno stratagemma. Fondandosi su un attestato scolastico del 22 aprile 2009, afferma poi che il rientro in Austria esporrebbe il ragazzo "a gravissime conseguenze" a livello psichico. Il ricorrente suggerisce anche al Tribunale federale di completare la perizia agli atti con riferimento alla volontà del figlio. Egli sostiene altresì che la Corte di appello avrebbe violato l'art. 13 cpv. 2 CArap, perché dalla perizia fatta allestire dall'autorità di vigilanza risulta chiaramente la volontà del ragazzo di rimanere in Ticino. Ritiene inoltre che il rapporto 16 aprile 2008 dell'Ufficio della gioventù di Salisburgo debba essere letto con prudenza, essendo stato allestito in un momento travagliato per C._ e che la qui opponente, a differenza del ricorrente, si era recata più volte in tale Ufficio. Asserisce pure che la famiglia della madre concorda sul fatto che il ragazzo debba vivere in Ticino. Il ricorrente considera infine assurdo far tornare a fine maggio in Austria il minore, non permettendogli così di terminare l'anno scolastico.
D.b Con risposta del 14 maggio 2009, B._ non ha formulato obiezioni alla sospensione dell'esecutività della sentenza impugnata, della quale ha chiesto la conferma con la consegna del figlio entro 15 giorni dall'emanazione della decisione di questo Tribunale. Ella postula pure di essere posta al beneficio dell'assistenza giudiziaria e del gratuito patrocinio in virtu dell'art. 26 CArap. Afferma che la CArap è applicabile, atteso che ella, vittima di due infarti, dopo essersi ristabilita, ha chiesto il rientro del figlio e che nel marzo 2008 si era limitata ad esercitare il suo diritto di custodia sulla prole. Asserisce inoltre che agli atti non risulta alcuna perizia, per altro mai chiesta dal ricorrente alle autorità inferiori, ma semplicemente un ascolto del minore e sostiene che il figlio viene manipolato dal padre.
D.c Con decreto del 19 maggio 2009 la Presidente della Corte adita ha conferito effetto sospensivo al ricorso nel senso che la sentenza impugnata non può essere eseguita.

Diritto:
1. 1.1 La sentenza impugnata è una decisione finale emanata dall'ultima autorità cantonale (art. 75 cpv. 1 e art. 90 LTF), fondata sulla CArap. Il ricorso in materia civile (art. 72 cpv. 2 lett. b n. 1 LTF; <ref-ruling> consid. 1.2), introdotto nel termine ricorsuale di 10 giorni previsto dall'art. 100 cpv. 2 lett. c LTF, è in linea di principio ammissibile.
1.2 Il Tribunale federale fonda la propria sentenza sui fatti accertati dall'autorità inferiore (<ref-law>), a meno che questi non sia stato svolto in modo manifestamente inesatto (art. 97 cpv. 1 e 105 cpv. 2 LTF). Giusta l'<ref-law> possono essere addotti nuovi fatti e nuovi mezzi di prova soltanto se ne dà motivo la decisione dell'autorità inferiore. Ciò significa che l'argomentazione attinente all'esposizione del ragazzo a "gravissime conseguenze" in caso di rientro in Austria, fondata su un documento allestito dopo l'emanazione della sentenza impugnata, si rivela di primo acchito inammissibile. Altrettanto irricevibili risultano le lettere scritte dai nonni e da C._ dopo la pronunzia della sentenza di appello nonché la domanda di allestire un "complemento peritale volto a confermare l'evoluzione di C._".
2. Il ricorrente non ritiene applicabile la CArap, perché i presupposti dell'art. 12 cpv. 1 della Convenzione non sarebbero adempiuti, atteso che l'opponente ha fatto rientrare in Austria il figlio con uno stratagemma. Considera inoltre "opportuno interrogarsi" se il fatto che l'opponente aveva acconsentito alla permanenza di C._ in Ticino dall'ottobre 2006 al marzo 2008 non costituisca un motivo per non ordinare il ritorno nel senso dell'art. 13 cpv. 1 CArap.
Ora, il ricorrente sembra dimenticare che quando egli, dopo le vacanze estive, ha disatteso le richieste dell'ex moglie e non ha fatto rientrare il figlio, C._ viveva nuovamente da oltre 4 mesi in Austria - dove era stato scolarizzato - che la madre, esclusiva detentrice dell'autorità parentale, esercitava tale diritto. Ne segue che la Convenzione dell'Aia in discussione è nella fattispecie applicabile (art. 1 lett. a e art. 3 CArap). Appare infatti del tutto irrilevante che la - in concreto incontestata - dimora abituale in Austria del minore prima del suo mancato ritorno sarebbe la conseguenza di uno stratagemma messo in atto dall'opponente, atteso che nemmeno un trasferimento illecito del minore esclude, da solo, la costituzione di una dimora abituale (<ref-ruling> consid. 2bb). In queste circostanze risulta pure ininfluente, con riferimento all'art. 13 cpv. 1 CArap, il fatto che la permanenza in Ticino del figlio dall'autunno 2006 alla primavera 2008 fosse avvenuta con il consenso della madre.
3. 3.1 Il ricorrente considera poi violato l'art. 13 cpv. 2 CArap, perché nonostante la chiara volontà del ragazzo di rimanere in Ticino, la Corte di appello ne ha ordinato il ritorno in Austria dalla madre.
3.2 L'ultima istanza cantonale ha indicato che per la psicologa che ha sentito su incarico dell'autorità ticinese di vigilanza sulle tutele C._, questi "non nutre alcun dubbio a livello razionale, né tanto meno alcuna ambivalenza emotiva sulla scelta della sua convivenza, ripete a diverse riprese e in modo pienamente convinto e anche sereno il suo determinato e deciso desiderio, anzi la sua scelta di voler continuare a vivere in Svizzera presso il papà e di non voler assolutamente fare ritorno in Austria". Dal rapporto di ascolto ripreso nella sentenza impugnata risulta che C._ ha indicato di voler continuare ad abitare con il padre perché si trova bene con lui, mentre afferma di non aver mai avuto un rapporto sereno con la madre, che lo sgridava ingiustamente. Risente un certo astio nei confronti di lei per avergli impedito di rientrare in Svizzera dopo le vacanze pasquali. Sempre dal rapporto di ascolto emerge che il ragazzo aveva vissuto tale fatto come una mancanza di lealtà della madre nei suoi confronti e che ha dichiarato di non aver vissuto bene i mesi estivi presso la mamma e di essere stato contento quando ha potuto partire per le vacanze in Italia nel paese del padre.
Da tali circostanze i Giudici cantonali hanno ritenuto che "non fa dubbio che C._ si trovi bene con il padre, viva altrettanto bene in Ticino e non intenda tornare dalla madre", ma che ciò non era sufficiente per respingere la richiesta di rientro. Essi hanno indicato che il figlio è stato messo sotto pressione da entrambi i genitori e a tal proposito citano l'audizione effettuata dall'Ufficio della gioventù di Salisburgo da cui risulta - incontestatamente - che il qui ricorrente ha minacciato il figlio di non volerlo più vedere e di suicidarsi se dovesse restare in Austria. Inoltre, dalla relazione 25 agosto 2008 del servizio sociale del Tribunale di Leibnitz emerge che C._ è lacerato dal conflitto dei genitori, volendo stare con entrambi, e non è in grado di decidere dove vivere perché non vuole ferire nessuno ed è disperato. Secondo i Giudici cantonali i rapporti con la madre non risultano irrimediabilmente compromessi e il ragazzo è vittima di un doloroso conflitto di lealtà. Essi concludono citando la recente giurisprudenza di questo Tribunale (<ref-ruling> consid. 4 pag. 91), secondo cui l'opposizione ai sensi dell'art. 13 cpv. 2 CArap, quale eccezione al principio del ritorno all'affidatario dei figli trasferiti illecitamente, non accorda al minore un diritto di scelta sul luogo in cui vivere con la famiglia e l'opposizione esternata dev'essere qualificata, ovvero decisa e intimamente giustificata da motivi plausibili.
3.3 In concreto, nell'ascolto effettuato in Ticino è stata effettivamente costatata la scelta di C._ di rimanere in Ticino dal padre. Tuttavia, il ricorrente non contesta in alcun modo che C._ sia vittima di un doloroso conflitto di lealtà. Inoltre, come indicato dalla Corte cantonale, il semplice desiderio di non rientrare presso il genitore affidatario non è sufficiente giusta la summenzionata giurisprudenza di questo Tribunale per non ordinare il ritorno. È invece necessaria un'opposizione qualificata e cioè ferma e sorretta da motivi plausibili. Se dal verbale di ascolto risulta un'opposizione ferma, essa non pare sorretta da ragioni plausibili idonee ad impedire un rientro del ragazzo in Austria: i motivi addotti per la sua scelta attengono più che altro al rapporto con i singoli genitori: tale questione concerne però in primo luogo l'affidamento e dev'essere risolta dal Tribunale del luogo di provenienza del minore rapito (art. 16 CArap). Giova del resto rilevare che - come la Svizzera - altri Stati firmatari della Convenzione in discussione non danno un valore assoluto alla preferenza espressa dal minore di cui è chiesto il ritorno, ma valutano pure la natura e la forza dell'opposizione (v. sentenza della Court of Appeal, Civil Division, inglese del 23 giugno 2005 in re Zaffino v. Zaffino con commento in «www.incadat.com», numero Incadat 813).
4. 4.1 Da quanto precede discende che il ricorso dev'essere respinto e la sentenza che ordina il ritorno confermata. Atteso che la LTF non prevede un ricorso adesivo, la richiesta formulata nella risposta dall'opponente di mettere a carico dello Stato le spese di rimpatrio non entra in linea di conto.
4.2 La procedura con la quale viene chiesto il ritorno del minore è gratuita (art. 26 cpv. 2 CArap), motivo per cui non vengono prelevate spese giudiziarie. Con riferimento agli onorari dei legali, la predetta gratuità si estende unicamente alla partecipazione di un avvocato ordinata dall'autorità coinvolta. Chi si lascia invece patrocinare volontariamente o rispettivamente in modo indipendente come è il caso per il qui ricorrente deve assumersi i costi del proprio legale, a meno che non siano dati i presupposti del diritto nazionale per il gratuito patrocinio (<ref-ruling> consid. 5, non pubblicato). Ora, al ricorrente indigente può nella fattispecie essere concesso il gratuito patrocinio (<ref-law>). L'assistenza giudiziaria si estende però unicamente ai costi di patrocinio del beneficiario e non anche alle ripetibili che egli, quale parte soccombente (<ref-law>), dovrà versare all'opponente. Atteso che anche quest'ultima, assistita da un'avvocata incaricata dall'autorità svizzera, ha chiesto al Tribunale federale di assumere il pagamento delle proprie spese legali, si giustifica in concreto, qualora non le fosse possibile riscuotere le ripetibili, far versare l'onorario alla sua legale dalla Cassa del Tribunale federale.

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto e a A._ è ordinato di assicurare il ritorno del figlio C._ a Gamlitz (Austria) dalla madre B._ entro il 6 luglio 2009.
2. La domanda di assistenza giudiziaria del ricorrente è accolta e gli è designato quale patrocinatore per la procedura innanzi al Tribunale federale l'avv. Francesca Lepori Colombo, alla quale la Cassa del Tribunale federale verserà un onorario di fr. 1'500.--.
3. Il ricorrente rifonderà all'opponente un'indennità di fr. 1'500.-- a titolo di ripetibili della sede federale. Se tale indennità non potrà essere incassata, la Cassa del Tribunale federale verserà all'avv. Patrizia Casoni Delcò un onorario di fr. 1'500.--.
4. Comunicazione ai patrocinatori delle parti e alla I Camera civile del Tribunale d'appello del Cantone Ticino.