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. 