Sachverhalt:
A. Die Parteien heirateten im Januar 1994 und lebten in der Folge in Australien. Der Ehe entstammen die Kinder X._, geb. 1996, und Y._, geb. 1998. Seit April 2000 sind die Parteien getrennt.
Im Juni 2001 entführte A._ die Kinder während eines in Australien hängigen Eheschutzverfahrens in die Schweiz, wo sie sich zunächst bei Verwandten in P._/VS niederliess. Nachdem ihr Mann im November 2001 beim Bezirksgericht Goms ein Rückführungsgesuch gestellt hatte, zog sie mit den Kindern nach L._/AG. Im Rahmen eines zweiten Rückführungsgesuchs verpflichtete das Obergericht des Kantons Aargau A._ mit rechtskräftigem Urteil vom 21. Oktober 2002, die beiden Kinder innerhalb von 10 Tagen und in Zusammenarbeit mit dem Bundesamt für Justiz nach Australien zurückzuführen. Sie entzog sich jedoch der per Ende April 2003 organisierten Rückführung, indem sie mit den Kindern unmittelbar vor dem Rückflug während drei Monaten auf einer Alp untertauchte und ihren Aufenthaltsort anschliessend nach Zürich verlegte.
B. Am 22. Januar 2004 wies der Einzelrichter im summarischen Verfahren des Bezirkes Zürich das von B._ gestellte Gesuch um Vollstreckung des aargauischen Rückführungsentscheides ab. Demgegenüber hiess das Obergericht des Kantons Zürich, II. Zivilkammer, das Gesuch mit Beschluss vom 17. März 2004 gut und wies das Gemeindeammannamt Zürich 1 an, das Rückführungsurteil des Obergerichts des Kantons Aargau vom 21. Oktober 2002 unverzüglich zu vollstrecken.
C. Gegen diesen Beschluss hat A._ am 12. April 2004 staatsrechtliche Beschwerde erhoben mit dem Begehren um dessen Aufhebung, eventualiter um Rückweisung der Sache an die Vorinstanz. Ausserdem hat sie die aufschiebende Wirkung und die unentgeltliche Rechtspflege verlangt.
Mit Präsidialverfügung vom 29. April 2004 ist die aufschiebende Wirkung erteilt worden, jedoch verbunden mit der Anordnung, dass die kantonal verfügten Massnahmen (Platzierung der Kinder im Kinderheim O._ bis zum rechtskräftigen Entscheid) in Kraft bleiben. In der Sache selbst sind keine Vernehmlassungen eingeholt worden.

Das Bundesgericht zieht in Erwägung:
1. Das Bundesgericht hat in seinem Entscheid 5P.160/2001 vom 13. September 2001 in E. 4b/aa festgehalten, dass die Vollstreckung eines Rückführungsentscheides, der gestützt auf das Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführungen (HEntfÜ, SR 0.211.230.02) gefällt worden ist, nicht von diesem Übereinkommen geregelt wird. Obwohl dieser Rechtsprechung Kritik erwachsen ist (namentlich Bucher, in: AJP 2002, S. 471 ff., sowie in: SZIER 2002, S. 99 ff.; ders., L'enfant en droit international privé, Genève 2003, N. 502; ferner Schmid, Neuere Entwicklungen im Bereich der internationalen Kindesentführungen, in: AJP 2002, S. 1338, Fn. 131), ist daran mangels einer ausdrücklichen Vollstreckungsregelung im Übereinkommen festzuhalten (vgl. Reeb, L'enlèvement international d'enfants par un parent en Suisse, in: Recueil de jurisprudence neuchâteloise 2002, S. 31; Hauser/Urwyler, Kindesentführungen, in: Rechtshilfe und Vollstreckung, Schriften der Stiftung für die Weiterbildung Schweizerischer Richterinnen und Richter [SWR], Band 5, Bern 2004, S. 77; Boéchat/Rusca-Clerc, Enlèvement d'enfants, in: Rechtshilfe und Vollstreckung, SWR Band 5, Bern 2004, S. 105). Dies entspricht auch der herrschenden Lehre in Deutschland, wo sich die Vollstreckung des Rückführungsentscheides nach dem Gesetz über die freiwillige Gerichtsbarkeit richtet (vgl. Siehr, in: Münchener Kommentar, 3. Aufl., 1998, N. 50 Anh. II zu Art. 19 EG BGB; Bach/Gildenast, Internationale Kindesentführung, Bielefeld 1999, N. 176; Vomberg/Nehls, Rechtsfragen der internationalen Kindesentführung, München 2000, S. 52). Indes sind das Beschleunigungsgebot gemäss Art. 11 HEntfÜ und das in Art. 12 Abs. 1 statuierte Gebot der sofortigen Rückgabe insofern auch im Vollstreckungsverfahren zu beachten, als die Zielsetzung des Übereinkommens nicht im Stadium der Vollstreckung unterlaufen werden darf. Nichts hindert im Übrigen die Kantone, in deren Kompetenz die Regelung der Vollstreckung fällt, bzw. die rechtsanwendenden kantonalen Instanzen, den materiellen Rückführungsentscheid mit einer eigentlichen Vollstreckungsklausel zu versehen (in diesem Sinn auch Reeb, a.a.O., S. 32; Schmid, a.a.O., S. 1338); das Rückführungsurteil bildet dann gleichzeitig den Vollstreckungstitel. Die Verbindung der materiellen Rückgabeanordnung mit einer entsprechenden Vollstreckungsanordnung wird namentlich in Deutschland praktiziert (Vomberg/Nehls, a.a.O., S. 112; vgl. ferner Krüger, Das Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführung, in: Monatsschrift für deutsches Recht [MDR] 1998, S. 697) und ist den kantonalen Behörden insbesondere für diejenigen Fälle anzuempfehlen, in denen keine Mitwirkung der rückgabepflichtigen Partei zu erwarten ist bzw. eine Organisation der Rückführung durch das Bundesamt für Justiz als zentrale Behörde gemäss Art. 6 Abs. 1 HEntfÜ nicht möglich scheint.
Vorliegend sind die aargauischen Behörden zwar so vorgegangen, hat doch das Obergericht des Kantons Aargau die Beschwerdeführerin in seinem Urteil vom 21. Oktober 2002 unter Androhung des polizeilichen Vollzuges und der Ungehorsamsstrafe gemäss <ref-law> im Unterlassungsfall verpflichtet, die beiden Kinder innert 10 Tagen nach Australien zurückzuführen. Indes hat sich die Beschwerdeführerin dem Vollzug des Rückführungsurteils mit ihrem Untertauchen entzogen, und wegen des anschliessenden Kantonswechsels musste der Beschwerdegegner im Kanton Zürich ein neues Vollstreckungsverfahren einleiten. Weil es sich demnach beim angefochtenen Beschluss des Obergerichts des Kantons Zürich, der die Vollstreckung des aargauischen Rückführungsentscheides anordnet, um ein reines Vollstreckungsurteil handelt, ist auf die staatsrechtliche Beschwerde insoweit nicht einzutreten, als nicht Vollstreckungshindernisse geltend gemacht werden (dazu E. 2), sondern materiell eine falsche Anwendung des Übereinkommens gerügt wird.
2. Zulässig im Rahmen der Staatsvertragsbeschwerde (Art. 84 Abs. 1 lit. c OG) ist der Hinweis auf Art. 3 des Übereinkommens über die Rechte des Kindes (UNO-Kindesrechtskonvention, KRK, SR 0.107), ist doch diese Konvention grundsätzlich auch im Vollstreckungsverfahren zu beachten. Allerdings missbilligt gerade die KRK in Art. 11 die Kindesentführung und fordert die Vertragsstaaten auf, den entsprechenden Übereinkommen beizutreten. Die KRK und das HEntfÜ verfolgen somit in Bezug auf die Rückführung widerrechtlich ins Ausland verbrachter Kinder die gleichen Ziele und insofern kann die Beschwerdeführerin aus der Konvention nichts für ihren Standpunkt ableiten. Insbesondere kann das in Art. 3 KRK erwähnte Kindeswohl im Vollstreckungsstadium nicht in dem Sinn oberste Leitmaxime sein, als der materielle Rückführungsentscheid als solcher in Frage gestellt oder gar die ganze Streitsache neu aufgerollt werden darf. Geprüft werden kann einzig, ob nach dem Rückführungsentscheid neue Tatsachen eingetreten sind, die dessen Vollstreckung im Lichte des HEntfÜ als unzumutbar erscheinen lassen. Weil im Vollstreckungsverfahren der Rückführungsentscheid nicht in Frage gestellt werden darf, können sodann - abgesehen von den Sonderfällen, dass das Kind in der Zwischenzeit das 16. Altersjahr vollendet hat (vgl. Art. 4 HEntfÜ) oder im Ursprungsstaat eine vom früheren Rechtszustand abweichende Sorgerechtsentscheidung ergangen ist, welche die Rückgabe hinfällig werden lässt - einzig solche Umstände in Betracht fallen, die vorübergehender Natur sind; zu denken ist etwa an die Transportunfähigkeit des Kindes wegen schwerer Erkrankung oder an die Rückführung in ein Katastrophengebiet. Dagegen ist es unzulässig, im Vollstreckungsverfahren eine dauerhafte Veränderung der Verhältnisse geltend zu machen, wie dies insbesondere bei einer erneuten Diskussion des in Art. 12 Abs. 2 HEntfÜ erwähnten Einlebens in der neuen Umgebung der Fall wäre. Insofern kann am Bundesgerichtsentscheid 5P.160/2001 vom 13. September 2001, mit dem im Rahmen des Vollstreckungsverfahrens letztlich die Abänderung bzw. Aufhebung des Rückführungsentscheides sanktioniert worden ist, nicht festgehalten werden.
Bei der Vollstreckung von Rückführungsentscheiden dürfen (und müssen) schliesslich bis zu einem gewissen Grad auch generalpräventive Gedanken eine Rolle spielen, hängt doch die Autorität des Übereinkommens im Wesentlichen von der Frage ab, ob die gestützt darauf ergehenden Urteile überhaupt vollzogen werden können (vgl. Botschaft zur Ratifikation des HEntfÜ, BBl 1983 I S. 105; Bucher, AJP 2002 S. 476; Kuhn, Ihr Kinderlein bleibet, so bleibet doch all, in: AJP 1997 S. 1105). In diesem Zusammenhang darf nicht ausser Acht gelassen werden, dass es sich beim HEntfÜ um ein gegenseitiges Abkommen handelt, das die Schweiz als Signatarstaat nicht nur in die Pflicht nimmt, sondern in einer ungefähr gleichen Anzahl von Fällen auch die Rückschaffung widerrechtlich entführter Kinder in die Schweiz ermöglicht. Nicht hinnehmbar ist unter rechtsstaatlichen Gesichtspunkten, dass der rückgabepflichtige Elternteil untertaucht oder sich durch steten Wohnsitzwechsel Selbstjustiz verschafft und die Rückführung des Kindes hintertreibt. Sodann darf nicht übersehen werden, dass ein allfälliger Schaden, der dem Kind aus dem Verbringen über die Landesgrenzen erwächst, auf der einseitigen Handlungsweise der entführenden Person beruht und diese allein für alle Unzuträglichkeiten verantwortlich ist, die aus der Korrektur ihres Fehlverhaltens entstehen (vgl. Kuhn, a.a.O., S. 1099). Deshalb kann sich auch nicht auf einen bestimmten Zustand oder eine Gefahr berufen, wer diesen bzw. diese selbst geschaffen hat (vgl. Siehr, a.a.O., N. 61a).
3. Unbeachtlich sind damit die Vorbringen, der Vater habe sich zu wenig um die Kinder gekümmert, der Beschwerdeführerin drohe bei einer Rückkehr nach Australien ein Strafverfahren und die Kinder hätten in Australien Sprach- und Integrationsschwierigkeiten. Diese Aspekte sind im Sachurteil berücksichtigt worden und haben sich seither nicht verändert. Mit Bezug auf die behauptete Unzumutbarkeit würde sich aber selbst dann nichts anderes ergeben, wenn vorliegend materiell über die Rückführung und nicht über die Vollstreckung der entsprechenden Anordnung zu befinden wäre: Es versteht sich von selbst, dass bei einer Rückführung in das Ursprungsland anfängliche Sprach- und Integrationsschwierigkeiten auftreten; dies ist eine fast zwangsläufige Erscheinung, die vom HEntfÜ bewusst in Kauf genommen wird (Urteile des Bundesgerichts 5P.310/2002 vom 18. November 2002, E. 3.4 i.f., und 5P.71/2003 vom 27. März 2003, E. 2.4.3; in diesem Sinn auch der Beschluss des deutschen Bundesverfassungsgerichts vom 15. Februar 1996, E. II.3, publ. in: IPrax 1997, S. 124). Ebenso wenig würde für sich genommen ein allfälliges Strafverfahren gegen den Entführer im Ursprungsstaat (Beschluss des deutschen Bundesverfassungsgerichts vom 18. Juli 1997, E. 3d, publ. in: NJW 1997, S. 3302; Kuhn, a.a.O., S. 1099; Vomberg/Nehls, a.a.O., S. 43) oder die mögliche Trennung eines Kindes von der Mutter einen Ausschlussgrund gemäss Art. 13 Abs. 1 lit. b HEntfÜ darstellen (von Staudinger/Pirrung, Kommentar zum Bürgerlichen Gesetzbuch, 13. Aufl., Berlin 1994, N. 683 und 684 Vorbem. zu Art. 19 EG BGB; Kuhn, a.a.O., S. 1099; Schmid, a.a.O., S. 1333; Bach/Gildenast, a.a.O., N. 131).
Von vornherein keine Rolle spielt im Vollstreckungsverfahren das behauptete Einleben in der Schweiz (vgl. E. 2). Abgesehen davon steht die Behauptung im Widerspruch zu den Akten. Aus diesen ergibt sich vielmehr das Bild einer labilen, von steten Ortswechseln geprägten Situation der Kinder, die weder schulisch richtig integriert sind noch in einem stabilen Umfeld aufwachsen und deren einzige Bezugsperson die Mutter ist.
Kein Raum besteht auf Grund der gemachten Ausführungen schliesslich für die Anordnung des geforderten kinderpsychologischen Gutachtens, umso weniger als bereits im materiellen Rückführungsverfahren das Beschleunigungsgebot (Art. 11 HEntfÜ) sowie die Tatsache, dass im Rückführungsprozess nicht über die Zuteilung des Sorgerechts, sondern einzig über das widerrechtliche Verbringen des Kindes und allfällige Einwände gegen dessen Rückführung zu befinden ist, für den Regelfall eine Begutachtung des Kindes ausschliessen (Vomberg/Nehls, a.a.O., S. 70; Kuhn, a.a.O., S. 1105; Schmid, a.a.O., S. 1333 und 1337, Fn. 124).
4. Zusammenfassend ergibt sich, dass die gegen den Vollstreckungsbeschluss des Obergerichts des Kantons Zürich gerichtete staatsrechtliche Beschwerde abzuweisen ist, soweit darauf eingetreten werden kann.
Der offensichtlich unbemittelten Beschwerdeführerin ist die unentgeltliche Rechtspflege zu erteilen (Art. 156 Abs. 1 OG), und es ist ihr Lisa Zaugg als amtliche Anwältin beizuordnen (Art. 156 Abs. 2 OG). Die der Beschwerdeführerin aufzuerlegende Gerichtsgebühr (Art. 156 Abs. 1 OG) ist demnach einstweilig auf die Gerichtskasse zu nehmen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Der Beschwerdeführerin wird die unentgeltliche Rechtspflege erteilt, unter Beiordnung von Lisa Zaugg als Rechtsanwältin.
3. Die Gerichtsgebühr von Fr. 3'000.-- wird der Beschwerdeführerin auferlegt, jedoch einstweilig auf die Bundesgerichtskasse genommen.
4. Rechtsanwältin Lisa Zaugg wird aus der Bundesgerichtskasse mit Fr. 3'000.-- entschädigt.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 18. Mai 2004
Im Namen der II. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: