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.