Sachverhalt:
A. Die Parteien haben am 26. April 1996 in A._ geheiratet. Spätestens seit Januar 1997 lebten sie in Brasilien. Dort kamen die beiden gemeinsamen Kinder V._, geb. 1997, und W._, geb. 1999, zur Welt. Im April 2004 trennten sich die Parteien; beide hielten sich weiterhin in Brasilien auf.
Im Mai 2006 reiste der Vater mit den Kindern für einen Ferienaufenthalt von einem Monat in die Schweiz. Die Mutter hatte die nach brasilianischem Recht notwendige schriftliche und beglaubigte Zustimmung zu einer Auslandreise der Kinder für die Zeit vom 3. Mai bis 3. Juni 2006 erteilt. Der Vater kehrte mit den Kindern nicht nach Brasilien zurück.
Mit Brief vom 30. August 2006 teilte der Dienst für internationalen Kindesschutz im Bundesamt für Justiz dem Bezirksgericht Bremgarten mit, ihre Partnerbehörde in Brasilien habe die Entführung der beiden Kinder gemeldet. Es liege ein Rückführungsantrag und eine richterliche Verfügung vom 21. Juli 2006 vor, wonach die Kinder wieder in die Obhut der Mutter zurückzuführen seien.
B. Mit Gesuch vom 7. September 2006 verlangte die Mutter die Rückführung der beiden Kinder. Mit Urteilen vom 10. Oktober und 18. Dezember 2006 verpflichteten sowohl das Bezirksgericht Bremgarten als auch das Obergericht des Kantons Aargau den Vater zur Rückführung der beiden Kinder.
C. Gegen das obergerichtliche Urteil hat der Vater am 30. Dezember 2006 eine staatsrechtliche Beschwerde erhoben mit dem Begehren um dessen Aufhebung und Rückweisung der Sache zur Neubeurteilung; sodann verlangt er die unentgeltliche Rechtspflege. In ihrer Vernehmlassung vom 9. Januar 2007 hat die Mutter auf Abweisung der Beschwerde geschlossen und ebenfalls die unentgeltliche Rechtspflege verlangt. Mit Präsidialverfügung vom 15. Januar 2007 wurde der Beschwerde antragsgemäss die aufschiebende Wirkung erteilt.

Das Bundesgericht zieht in Erwägung:
1. Am 1. Januar 2007 ist das Bundesgesetz über das Bundesgericht (BGG; SR 173.110) in Kraft getreten (AS 2006 1205, 1243). Der angefochtene Entscheid ist vorher ergangen, so dass noch die Bestimmungen des Bundesrechtspflegegesetzes (OG) anzuwenden sind (vgl. Art. 132 Abs. 1 BGG).
Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darstellung darüber enthalten, welche Rechtssätze und inwiefern sie durch den angefochtenen Entscheid verletzt worden sind (Art. 90 Abs. 1 lit. b OG). Das Bundesgericht prüft nur klar und detailliert erhobene Rügen (<ref-ruling> E. 1c S. 76; <ref-ruling> E. 1.6 S. 189; <ref-ruling> E. 1.3 S. 262). Soweit sich diese auf Konventionsverletzungen beziehen, werden sie im Verfahren der Staatsvertragsbeschwerde mit freier Kognition geprüft (Art. 84 Abs. 1 lit. c OG; <ref-ruling> E. 3b S. 455, 130 III 489 E. 1.4 S. 492).
2. Der Beschwerdeführer macht in erster Linie geltend, die kantonalen Instanzen hätten die Kinder anhören müssen, und er rügt in diesem Zusammenhang eine Verletzung von Art. 13 Abs. 2 des Haager Übereinkommens über die zivilrechtlichen Aspekte internationaler Kindesentführung (HEntfÜ; SR 0.211.230.02), wonach das Gericht die Rückgabe des Kindes ablehnen kann, wenn festgestellt wird, dass es sich dieser widersetzt und dass es ein Alter und eine Reife erreicht hat, angesichts deren es angebracht erscheint, seine Meinung zu berücksichtigen.
2.1 Das Obergericht hat diesbezüglich erwogen, gemäss den Aussagen der Beschwerdegegnerin hätten die Kinder Heimweh nach Brasilien, während der Beschwerdeführer ausgesagt habe, der jüngere Sohn W._ wolle nicht nach Brasilien zurück, wobei er hierfür keine eigentlichen Gründe genannt habe. Auffällig sei zudem, dass der ältere Sohn V._ auf die Frage, was er wolle, wenn der Vater nach Brasilien gehe, die Mutter aber in der Schweiz bleibe, geantwortet haben soll, dann gehe er mit dem Vater nach Brasilien; erst auf die Aufforderung, sich dies noch einmal zu überlegen, habe er gesagt, er wolle in der Schweiz bleiben. Die vom Beschwerdeführer wiedergegebene spontane Antwort von V._ zeige deutlich, dass er keine Vorbehalte gegen Brasilien habe, sondern allenfalls die Betreuung durch den Vater derjenigen durch die Mutter vorziehe.
Der bezüglich Art. 13 Abs. 2 HEntfÜ abzuklärende Sachverhalt sei untrennbar mit der Urteilsfähigkeit des Kindes verbunden; könne aber ein allfälliger Widerstand des Kindes mangels Alters und Reife nicht berücksichtigt werden, sei auf dessen Anhörung zu verzichten. Die beiden Kinder seien mit neun Jahren und vier Monaten (V._) bzw. sieben Jahren und sieben Monaten (W._) deutlich unter der aus psychologischer Sicht für die Annahme der Urteilsfähigkeit bezüglich Fragen der vorliegend sich stellenden Art postulierten Altersgrenze von elf bis dreizehn Jahren. Dazu komme, dass auch nach den Schilderungen des Beschwerdeführers die Kinder offenbar keine konkreten Gründe genannt hätten, weshalb sie nicht nach Brasilien zurückkehren möchten. Die vom Beschwerdeführer wiedergegebenen Äusserungen von V._ seien zudem ambivalent und bezögen sich nicht auf die Umstände in Brasilien, sondern auf die persönliche Beziehung zu den Eltern und damit auf eine Frage, die im Rückführungsverfahren keine Rolle spiele.
2.2 Das Bundesgericht hat in <ref-ruling> als Richtlinie festgehalten, dass die Kinderanhörung im Sinn von Art. 144 ZGB grundsätzlich ab dem vollendeten sechsten Altersjahr möglich ist. Der Beschwerdeführer möchte diese Rechtsprechung auf Art. 13 Abs. 2 HEntfÜ übertragen wissen. Er beruft sich dabei auf den von der zuständigen eidgenössischen Expertenkommission gemachten Entwurf zu einem Bundesgesetz über internationale Kindesentführungen und auf die Ausführungen des Kommissionspräsidenten in einem ergänzenden Bericht zum Schlussbericht der Expertenkommission, in welchen nach Ansicht des Beschwerdeführers für ein gleiches Schwellenalter im Zusammenhang mit dem HEntfÜ plädiert wird.
Die Beschwerdegegnerin macht geltend, bei der Anwendung des Haager Übereinkommens gehe es nicht um die Frage der Obhut oder des Sorgerechts, sondern allein um diejenige der Rückführung. Bezüglich dieser Frage müssten die Kinder urteilsfähig sein, und sie müssten in abstrakter Weise nachvollziehen und auseinanderhalten können, dass es nicht darum gehe, ob sie lieber beim Vater oder bei der Mutter sein möchten. Massgeblich müsse deshalb dasjenige Alter sein, ab welchem formallogische Denkoperationen möglich würden; dies sei ab elf bis dreizehn Jahren der Fall.
2.3 Im Zusammenhang mit der Verwertbarkeit von Aussagen im Sinn von Art. 13 Abs. 2 HEntfÜ hat das Bundesgericht in <ref-ruling> erwogen, dass sich nicht allgemein bestimmen lasse, ab welchem Alter das Kind über die für eine möglichst autonome Willensbildung erforderliche Reife verfügt. Es hat sodann auf die einschlägige Literatur verwiesen, welche diese Frage ebenfalls nicht einheitlich beantwortet (frühestens ab zehn Jahren: Schmid, Neuere Entwicklungen im Bereich der internationalen Kindesentführungen, in: AJP 2002, S. 1335; frühestens ab vierzehn Jahren: Kuhn, Ihr Kinderlein bleibet, so bleibet doch all, in: AJP 1997, S. 1102; Bach/ Gildenast, Internationale Kindesentführung, Bielefeld 1999, S. 61; Krüger, Das Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführung, in: MDR 1998, S. 696; je nach individuellem Reifegrad ab zehn bis vierzehn Jahren: Zürcher, Kindesentführung und Kindesrechte, Diss. Zürich 2005, S. 204 oben; gegen ein bestimmtes Mindestalter: Bucher, L'enfant en droit international privé, Basel 2003, S. 168 Rz. 486; Winkler von Mohrenfels, Der Kindeswille im Rahmen des Haager Kindesentführungsübereinkommens, in: Einheit und Vielfalt des Rechts, Festschrift für Reinhold Geimer zum 65. Geburtstag, München 2002, S. 1532 f.), und im Anschluss erwogen, auf jeden Fall sei die nötige Reife des Kindes umso eher zu bejahen, je näher es sich bei der für die Anwendung des Übereinkommens geltenden Altersgrenze von 16 Jahren befinde (E. 5.2 S. 340 m.w.H.).
Der vorliegende Fall ist insofern anders gelagert, als es nicht um die Frage geht, inwieweit die Aussagen angehörter Kinder - diese waren im zitierten Entscheid 9 1/2- bzw. 10 1/2-jährig - im Rückführungsentscheid zu berücksichtigen sind, sondern um diejenige, ob das Haager Übereinkommen die Anhörung der 7 1/2- bzw. gut 9-jährigen Knaben gebietet. Diese Frage ist im Folgenden zu prüfen.
2.4 Wie die Vorinstanzen und die Beschwerdegegnerin richtig festhalten, darf beim Rückführungsentscheid weder über die elterliche Sorge noch über die Obhut befunden werden; vielmehr bleibt die betreffende Entscheidung dem Richter des Herkunftsstaats vorbehalten (Art. 16 und 19 HEntfÜ; <ref-ruling> E. 5.3 S. 341). Alleiniges Thema des Rückführungsprozesses ist die Prüfung der Voraussetzungen für die Rückführung (namentlich das widerrechtliche Verbringen im Sinn von Art. 3 HEntfÜ). Sind diese erfüllt, ist die Rückführung grundsätzlich anzuordnen, soweit nicht einer der eng gefassten Ausschlussgründe gegeben ist (insbesondere Nichtausübung des Sorgerechts und Unzumutbarkeit der Rückführung gemäss Art. 13 Abs. 1 HEntfÜ sowie Weigerung des Kindes zur Rückkehr nach Art. 13 Abs. 2 HentfÜ).
Die erforderliche Reife im Sinn von Art. 13 Abs. 2 HEntfÜ hat ein Kind erreicht, wenn es in der Lage ist, den Sinn und die Problematik des anstehenden Rückführungsentscheides zu verstehen. Es muss insbesondere in der Lage sein zu erkennen, dass es nicht um das Sorgerecht oder die Obhut, sondern einzig darum geht, den aufenthaltsrechtlichen status quo ante wiederherzustellen, und es muss ihm auch bewusst sein, dass über die Frage, in welchem Land und bei welchem Elternteil es künftig leben soll, nach seiner Rückführung in den Ursprungsstaat von den dortigen Gerichten zu entscheiden ist (Winkler von Mohrenfels, a.a.O., S. 1533 f.).
Ab wann ein Kind dazu in der Lage ist, lässt sich nicht für alle Fälle und denkbaren Konstellationen einheitlich beantworten. Wie die Hinweise in E. 2.3 zeigen, wird in der Literatur ein Mindestalter zwischen zehn und vierzehn Jahren postuliert. Das Bundesgericht hat in <ref-ruling> E. 5.2 S. 340 festgehalten, auf jeden Fall sei die nötige Reife des Kindes umso eher zu bejahen, je näher es sich bei der für die Anwendung des Übereinkommens geltenden Altersgrenze von 16 Jahren befinde.
Dies stimmt mit der kinderpsychologischen Erkenntnis überein, dass formallogische Denkoperationen erst ab ungefähr elf bis zwölf Jahren möglich sind und auch die emotionale sowie kognitive Reife zu überdauernder eigener Meinungsbildung erst ab diesem Alter vorhanden ist (vgl. Felder/Nufer, Richtlinien für die Anhörung des Kindes aus kinderpsychologischer/kinderpsychiatrischer Sicht gemäss Art. 12 der UNO-Konvention über die Rechte des Kindes, in: SJZ 1999, S. 318; dieselben, Die Anhörung des Kindes aus kinderpsychologischer Sicht, in: Vom alten zum neuen Scheidungsrecht, Bern 1999, N. 4.131; Nufer, Die Kommunikationssituation bei der Anhörung von Kindern, in: SJZ 1999, S. 317, sowie in: ZVW 1999, S. 209).
2.5 Nichts ableiten kann der Beschwerdeführer aus dem Entwurf eines Gesetzes. Weder stehen dessen definitive Formulierung noch dessen Verabschiedung und Inkrafttreten fest, und im Übrigen operiert die einschlägige Bestimmung des Entwurfs explizit mit Blankettbegriffen und nennt kein bestimmtes Alter für die Anhörung.
Zu prüfen ist hingegen, ob in Abweichung zum bisher Gesagten die in <ref-ruling> für die Kinderanhörung gemäss Art. 144 ZGB genannte Richtlinie von sechs Jahren auch für diejenige im Rückführungsverfahren allgemein bzw. für diejenige gemäss Art. 13 Abs. 2 HEntfÜ im Speziellen massgeblich sein soll, wie dies vom Beschwerdeführer gefordert wird, oder ob das Kind hierfür ein Alter in der von der kinderpsychologischen Literatur genannten Bandbreite erreicht haben muss.
2.6 Das Bundesgericht hat im erwähnten <ref-ruling> betont, dass die Anhörung im Zusammenhang mit Obhuts- und Sorgerechtsfragen keine Urteilsfähigkeit des Kindes im Sinn von Art. 16 ZGB voraussetzt, da es bei kleineren Kindern in erster Linie darum geht, dass sich das urteilende Gericht ein persönliches Bild machen kann und über eine zusätzliche Erkenntnisquelle bei der Sachverhaltsfeststellung und Entscheidfindung verfügt. Bei ihnen ist deshalb auch nicht nach konkreten Zuteilungswünschen zu fragen, da sie sich hierüber noch gar nicht losgelöst von zufälligen gegenwärtigen Einflussfaktoren äussern und in diesem Sinn eine stabile Absichtserklärung abgeben können (E. 1.2.2 S. 557 m.H. auf die weiterführende Literatur).
Zum einen dürfen im Rückführungsentscheid diejenigen Faktoren, zu deren Erstellung die Aussagen kleinerer Kinder sehr gut beitragen können (aktuelle Situation, persönliche Beziehung zu den Elternteilen etc.), gerade nicht berücksichtigt werden. Zum anderen sind kleinere Kinder mit Bezug auf das Thema des Rückführungsprozesses noch gar nicht urteilsfähig. Die Befragung bei der Anhörung lässt sich aber nicht vom Gegenstand trennen, der im betreffenden Verfahren zu beurteilen ist. Es würde keinen Sinn machen, kleinere Kinder, welche die besondere Problematik des Rückführungsentscheides noch nicht erfassen können, bloss zu ihrer Situation im Allgemeinen anzuhören, wenn das Haager Übereinkommen zwingend vorgibt, dass diese (mit Ausnahme des Einlebens gemäss Art. 12 Abs. 2 HEntfÜ) im Rückführungsentscheid keine Rolle spielen kann.
Mit Blick auf die Willensbildung im Sinn von Art. 13 Abs. 2 HEntfÜ darf sodann nicht übersehen werden, dass in fast allen Entführungsfällen namentlich kleinere Kinder mit dem Entführer notwendigerweise eine Schicksalsgemeinschaft bilden und sie deshalb mit einer zwingenden Anhörung oftmals in eine unzumutbare Lage gebracht würden. Anders als die im Rahmen von Art. 144 und 314 ZGB anzuhörenden Kinder halten sie sich nicht in einer ihnen vertrauten Umgebung auf, sprechen sie oft eine andere Sprache und verfügen sie aufgrund der Entführungssituation nicht über eine Vielzahl von Bezugspersonen (Elternteile, Verwandte, Kameraden, etc.). Im Unterschied zu anderen Kindern dürften sie aufgrund der sich aus der Entführungssituation ergebenden Isolation in der Regel weniger einem Loyalitätskonflikt zwischen den beiden Elternteilen ausgesetzt sein, als vielmehr unter starkem Druck und entscheidendem Einfluss des entführenden Elternteils stehen. In diesem Sinn hat das Bundesgericht im bereits mehrfach erwähnten <ref-ruling> denn auch festgehalten, dass beim anzuhörenden Kind geprüft werden muss, ob es sich einer Rückführung aus freien Stücken widersetzt, und dass in diesem Sinn der beachtliche Kindeswillen vom manipulierten und deshalb unbeachtlichen abzugrenzen ist (E. 5.1 S. 339 f. m.w.H.).
Vor diesem Hintergrund ist es nicht angebracht, im Rückführungsverfahren kleinere Kinder systematisch anzuhören. Namentlich die Unterscheidung zwischen der Wiederherstellung des aufenthaltsrechtlichen status quo ante und dem Sorgerecht bzw. der Obhut, aber auch das Bewusstsein, dass über Letzteres nach der Konzeption des Übereinkommens der Richter im Herkunftsstaat zu entscheiden hat und die Frage, bei wem das Kind künftig leben soll, erst in jenem Verfahren thematisiert werden kann, ist relativ abstrakt, und entsprechende Denkoperationen sind einem Kind nach der zitierten kinderpsychologischen Literatur vor elf bis zwölf Jahren in aller Regel nicht möglich.
2.7 Bei dieser Ausgangslage hat das Obergericht kein Konventionsrecht verletzt, wenn es von einer Anhörung der altersmässig deutlich unter der genannten Bandbreite liegenden Knaben abgesehen hat.
3. Was den Rückführungsausschlussgrund von Art. 13 Abs. 1 lit. b HEntfÜ anbelangt, macht der Beschwerdeführer geltend, in diesem Zusammenhang erweise sich die Nichtanhörung der Kinder als willkürlich, liege doch willkürliche Beweiswürdigung namentlich vor, wenn der Sachrichter aus dem Ergebnis des Beweisverfahrens voreilige Schlüsse ziehe oder wenn er einseitig einzelne Beweise berücksichtige und andere ausser Betracht lasse.
Die Nichtanhörung als solche ist nicht eine Frage der Beweiswürdigung und verletzt das Übereinkommen nach dem vorstehend Ausgeführten nicht. Dass die Kinder durch die Rückführung einen körperlichen oder seelischen Schaden im Sinn von Art. 13 Abs. 1 lit. b HEntfÜ erleiden würden, macht der Beschwerdeführer vor Bundesgericht nicht geltend, weshalb die sinngemässe Rüge, die betreffende Bestimmung sei verletzt, unsubstanziiert bleibt und auf sie nicht eingetreten werden kann.
4. Zusammenfassend ergibt sich, dass die staatsrechtliche Beschwerde abzuweisen ist, soweit auf sie einzutreten ist. Aufgrund der gewährten aufschiebenden Wirkung ergibt sich, dass die dem Beschwerdeführer in Ziff. 1.1 des Dispositivs des angefochtenen Entscheides gesetzte Frist zur Rückführung erst mit der Zustellung des bundesgerichtlichen Urteils zu laufen beginnt.
5. Aufgrund des Verfahrensausgangs wird der Beschwerdeführer grundsätzlich kosten- und entschädigungspflichtig (Art. 156 Abs. 1 und Art. 159 Abs. 2 OG). Beide Parteien sind jedoch offensichtlich mittellos, weshalb ihnen die unentgeltliche Rechtspflege zu erteilen ist (Art. 152 Abs. 1 OG), für die Beschwerdegegnerin unter Beigabe von Roger Müller als unentgeltlichem Rechtsanwalt (Art. 152 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Beiden Parteien wird die unentgeltliche Rechtspflege erteilt, und der Beschwerdegegnerin wird Roger Müller als unentgeltlicher Rechtsanwalt beigegeben.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt, jedoch einstweilen auf die Bundesgerichtskasse genommen.
4. Roger Müller wird für das bundesgerichtliche Verfahren mit Fr. 2'000.-- entschädigt.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, Zivilgericht, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 13. Februar 2007
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: