Sachverhalt:
A. X._ (Ehemann) und Y._ (Ehefrau) heirateten am 30. August 1989 in A._ und wohnten in der Folge in Spanien. Am 5. März 1994 wurde der Sohn V._ und am 6. April 1995 der Sohn W._ geboren. Zusammen mit den beiden Söhnen verliess Y._ am 21. Juni 2003 Spanien und liess sich in A._ nieder. Zwei Tage später reichte sie beim Amtsgericht B._ eine Klage auf Scheidung der Ehe ein. Seit dem 25. Juni 2003 ist ausserdem ein Massnahmenverfahren nach <ref-law> hängig. Beide Verfahren sind zur Zeit sistiert.
B. B.a X._ stellte am 19. Januar 2004 beim Ministerio de Justicia in Madrid ein Gesuch um Rückführung der beiden Söhne V._ und W._ nach Spanien, das am 8. März 2004 an das Bundesamt für Justiz überwiesen und von diesem am 23. April 2004 an das Amtsgericht B._ weitergeleitet wurde. Mit Eingabe vom 19. Mai 2004 an dieses Gericht erneuerte X._ das Rückführungsgesuch.
B.b Der Amtsgerichtspräsident II von B._ hiess das Begehren mit Entscheid vom 21. Juni 2004 gut und verpflichtete Y._, die Kinder innert 30 Tagen ab Rechtskraft des Entscheids nach Spanien zurückzuführen.
Y._ zog den Entscheid an das Obergericht (II. Kammer) des Kantons Luzern weiter, das die Nichtigkeitsbeschwerde am 11. August 2004 guthiess, soweit es darauf eintrat, den Entscheid des Amtsgerichtspräsidenten aufhob und die Sache zu neuer Beurteilung an diesen zurückwies.
B.c Nach erneuter Instruktion wies der Amtsgerichtspräsident II von B._ das Rückführungsgesuch am 22. September 2004 ab.
Die von X._ hiergegen erhobene Nichtigkeitsbeschwerde wies das Obergericht (II. Kammer) am 11. November 2004 ab.
C. In seiner staatsrechtlichen Beschwerde vom 3. Januar 2005 beantragt X._, den obergerichtlichen Entscheid vom 11. November 2004 aufzuheben und die kantonale Instanz anzuweisen, das Rückführungsgesuch gutzuheissen und die Modalitäten der Rückführung festzulegen. Mit Eingabe vom 21. Januar 2005 hat er ausserdem um Gewährung der unentgeltlichen Rechtspflege nachgesucht.
Y._ beantragt, die Beschwerde abzuweisen, soweit darauf überhaupt einzutreten sei.
Das Obergericht hat sich nicht vernehmen lassen.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Die Auseinandersetzung über die Rückführung eines Kindes nach dem Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführung (HEntfÜ; SR 0.211.230.02) stellt keine Zivilrechtsstreitigkeit dar. Es geht in diesem Verfahren vielmehr um eine Art administrative Rechtshilfe zwischen den Vertragsstaaten. Damit steht gegen Entscheide über Rückführungsgesuche die Berufung nicht offen, so dass sich die staatsrechtliche Beschwerde als zulässig erweist (<ref-ruling> E. 1a S. 421).
1.2 Bei der Staatsvertragsbeschwerde überprüft das Bundesgericht Konventionsverletzungen frei (<ref-ruling> E. 1.4 S. 492; <ref-ruling> E. 3 S. 439). Hingegen beschränkt sich die Kognition hinsichtlich der Sachverhaltsfeststellungen auf eine Willkürprüfung, falls sich die Beschwerde - wie hier - gegen den Entscheid einer gerichtlichen Instanz richtet (<ref-ruling> E. 1.3 S. 111 f.). In einem solchen Fall ist das Vorbringen von Noven unzulässig (<ref-ruling> E. 6c S. 357 f.).
Soweit die Parteien Beweise einreichen und die Edition von Akten sowie die Einvernahme von Zeugen beantragen, können ihre Begehren demnach nicht berücksichtigt werden. Ebenso wenig ist auf tatsächliche Vorbringen einzutreten, es sei denn, es werde dem Obergericht eine willkürliche Beweiswürdigung (<ref-law>) oder eine Missachtung des rechtlichen Gehörs (<ref-law>) vorgeworfen oder geltend gemacht, die Sachverhaltsfeststellungen der kantonalen Instanz seien offensichtlich unvollständig. Das trifft insbesondere auf die einlässliche Schilderung der Lebensverhältnisse der Parteien in Spanien durch die Beschwerdegegnerin zu.
2. Der Beschwerdeführer beanstandet die bisherige Dauer des Verfahrens.
2.1 In Verfahren um Rückgabe von Kindern haben die zuständigen Behörden eines jeden Vertragsstaates mit der gebotenen Eile zu handeln (Art. 11 Abs. 1 HEntfÜ). Hat das zuständige Gericht nicht innerhalb von sechs Wochen nach Eingang des Antrags eine Entscheidung getroffen, so kann unter anderem der Gesuchsteller eine Darstellung der Gründe für die Verzögerung verlangen (Art. 11 Abs. 2 HEntfÜ). Das Übereinkommen konkretisiert demnach das allgemein geltende Beschleunigungsgebot wie es für Spanien und für die Schweiz nach Konventionsrecht (Art. 6 Abs. 1 EMRK) und für das Verfahren vor den Schweizer Behörden nach der Bundesverfassung (Art. 29 Abs. 1) gilt.
2.2 Vorliegend steht einzig die Dauer des Rückführungsverfahrens vor den Schweizer Behörden zur Beurteilung. Hingegen steht es dem Bundesgericht nicht zu, die Umstände zu prüfen, die dazu geführt haben, dass das am 19. Januar 2004 beim Ministerio de Justicia in Madrid eingereichte Gesuch erst am 8. März 2004 an das Bundesamt für Justiz in Bern überwiesen wurde. Das Bundesamt leitete das Gesuch seinerseits am 23. April 2004 an das Amtsgericht B._ weiter. Ob dieses Vorgehen in zeitlicher Hinsicht angebracht war, kann offen bleiben. Entscheidend ist nämlich die Gesamtdauer des Verfahrens vor den Schweizer Behörden. Der Amtsgerichtspräsident beurteilte das vom Bundesamt übermittelte, vom Beschwerdeführer am 19. Mai 2004 erneuerte Gesuch bereits am 21. Juni 2004. Das Obergericht entschied über die gegen den Gutheissungsentscheid erhobene Nichtigkeitsbeschwerde am 11. August 2004 und hob ihn auf. Hierauf ergänzte der Amtsgerichtspräsident das Beweisverfahren, indem er die beiden betroffenen Kinder anhörte, und entschied am 22. September 2004 von neuem. Das Obergericht schützte den Abweisungsentscheid des Amtsgerichts am 11. November 2004.
2.3 Aus dem Dargelegten ergibt sich, dass die Schweizer Behörden über das Rückführungsgesuch (mit zwei kantonalen Rechtsmittelverfahren) innert sieben Monaten befunden haben. Die jeweilige Entscheid- bzw. Rechtsmittelinstanz hat innert der Frist von sechs Wochen oder wenig mehr geurteilt. Dabei ist nicht ausser Acht zu lassen, dass die Gerichte den Parteien selbstverständlich das Anhörungsrecht zu gewähren hatten (<ref-law>) und ihnen die gesetzlichen Fristen und damit den Rechtsschutz nicht hatten abkürzen dürfen (dazu Alexander R. Markus, Beschleunigungsgebot und Berufungsfähigkeit bei Kinder-Rückgabeentscheiden nach Haager Übereinkommen, in: AJP 1997, S. 1086). Es fällt in diesem Zusammenhang übrigens auf, dass der Beschwerdeführer die Rechtsmittelfristen, einschliesslich der Gerichtsferien, im kantonalen Verfahren und bei der Einreichung der staatsrechtlichen Beschwerde jeweils voll ausgenützt hat. Die Angelegenheit wurde gesamthaft gesehen mit der gebotenen Eile behandelt, womit sich die betreffende Rüge als ungerechtfertigt erweist.
3. 3.1 Das Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführung hat unter anderem zum Ziel, die sofortige Rückgabe widerrechtlich in einen Vertragsstaat verbrachter oder dort zurückgehaltener Kinder sicherzustellen (Art. 1 lit. a). Als widerrechtlich gilt das Wegbringen oder Zurückhalten eines Kindes, wenn dadurch das Sorgerecht verletzt wird, das einer Person allein oder gemeinsam nach dem Recht des Staates zusteht, in dem das Kind unmittelbar vor dem Wegbringen oder Zurückhalten seinen gewöhnlichen Aufenthalt hatte (Art. 3 Abs. 1 lit. a HEntfÜ). Ist ein Kind im Sinne dieser Bestimmung widerrechtlich weggebracht oder zurückgehalten worden und ist bei Eingang des Antrags bei dem Gericht oder der Verwaltungsbehörde des Vertragsstaates, in dem sich das Kind befindet, eine Frist von weniger als einem Jahr seit dem Wegbringen oder Zurückhalten verstrichen, so wird die sofortige Rückgabe des Kindes angeordnet (Art. 12 Abs. 1 HEntfÜ).
Es steht im vorliegenden Verfahren fest und wird von den Parteien nicht bestritten, dass diese das Sorgerecht über die beiden Kinder in Spanien gemeinsam ausgeübt haben und die Jahresfrist für das Rückführungsgesuch eingehalten worden ist.
3.2 Art. 12 Abs. 2 HEntfÜ bestimmt, dass die Rückgabe des Kindes ebenfalls dann angeordnet wird, wenn der Antrag erst nach Ablauf der erwähnten Jahresfrist eingegangen ist, es sei denn, es sei erwiesen, dass das Kind sich in seiner neuen Umgebung eingelebt hat. Letzteres kann im vorliegenden Fall, wo das Gesuch früher gestellt worden ist, einer Rückführung mithin von vornherein nicht entgegenstehen. Soweit der Wunsch von V._ und W._, in der Schweiz zu bleiben, mit dem Hinweis auf die aktuellen Lebensumstände und die Beziehungen zu den hier lebenden Grosseltern begründet wird (vgl. unten E. 5.5), sind die Aussagen der Kinder mithin unbeachtlich.
4. 4.1 Nach Art. 13 Abs. 1 HEntfÜ ist die zuständige Instanz des ersuchten Staates nicht verpflichtet, die Rückgabe des Kindes anzuordnen, wenn nachgewiesen wird, dass der Gesuchsteller dem Wegbringen oder Zurückhalten zugestimmt oder dieses nachträglich genehmigt hat (lit. a) oder dass die Rückgabe mit der schwerwiegenden Gefahr eines körperlichen oder seelischen Schadens für das Kind verbunden wäre oder das Kind auf andere Weise in eine unzumutbare Lage brächte (lit. b). Ferner kann die Anordnung einer Rückgabe abgelehnt werden, wenn festgestellt wird, dass sich das Kind der Rückgabe widersetzt und es ein Alter und eine Reife erreicht hat, angesichts deren es angebracht erscheint, seine Meinung zu berücksichtigen (Art. 13 Abs. 2 HEntfÜ).
4.2 Der Amtsgerichtspräsident hatte dafür gehalten, dass alle drei eine Rückführung ausschliessenden Tatbestände gegeben seien. Demgegenüber gelangte das Obergericht zur Auffassung, dass einerseits bei einer Gesamtwürdigung der Verhältnisse ein nachträglicher Verzicht des Beschwerdeführers auf eine Rückführung der Kinder zu verneinen sei und dass andererseits von einer schwerwiegenden Gefahr für die körperliche oder seelische Gesundheit der Kinder im Falle ihrer Rückführung nicht gesprochen werden könne, zumal nicht dargetan sei, dass die von der Beschwerdegegnerin kritisierten Erziehungsmethoden des Beschwerdeführers und das sektenähnliche Umfeld, in dem die Familie gelebt habe, sich auch dann auf die Kinder auswirken würden, wenn diese bloss auf spanisches Hoheitsgebiet zurückgeführt würden. Als erfüllt hat das Obergericht jedoch den Ausschlussgrund von Art. 13 Abs. 2 HEntfÜ betrachtet.
4.3 In Anbetracht der Tatsache, dass ihrem Antrag auf Nichtrückgabe der Kinder gestützt auf diese Bestimmung stattgegeben worden ist, hatte die Beschwerdegegnerin keinen Anlass, den Entscheid des Obergerichts anzufechten. Dies hätte sie jedoch nicht daran gehindert, für den Fall, dass die Voraussetzungen von Art. 13 Abs. 2 HEntfÜ von der erkennenden Abteilung verneint werden sollten, sich auf die anderen Ausschlussgründe zu berufen und den obergerichtlichen Entscheid in dieser Hinsicht zu kritisieren. Da sie dies unterlassen hat, geht es im Folgenden einzig um die Frage, ob die Rückführung wegen eines von den Kindern geäusserten Widerstandes zu verweigern sei.
5. V._ und W._ wurden am 14. September 2004 (zunächst getrennt) in Anwesenheit eines Kinder- und Jugendpsychologen durch den Amtsgerichtspräsidenten von B._ angehört. Beide äusserten den Wunsch, nicht nach Spanien zurückkehren zu müssen.
5.1 Ob im Sinne von Art. 13 Abs. 2 HEntfÜ dem Widerstand des betroffenen Kindes Rechnung zu tragen und von der Anordnung seiner Rückführung in das Herkunftsland abzusehen sei, ist letztlich auf Grund einer sämtliche Umstände erfassenden Würdigung seiner Äusserungen zu beurteilen. Es ist zu prüfen, ob das (urteilsfähige) Kind sich einer Rückführung aus freien Stücken, d.h. unbeeinflusst durch den entführenden Elternteil, widersetzt (dazu Palandt/Heldrich, Beck' scher Kurz-Kommentar zum [Deutschen] Bürgerlichen Gesetzbuch, 64. Auflage, Anh. zu EGBGB 24 [IPR] Rz. 79). Zur Beantwortung dieser Frage ist abzuklären, inwieweit das Kind die Interessen der beiden betroffenen Eltern und seine eigene Situation zu erkennen und zu begreifen vermag und inwieweit es in der Lage ist, einen allfälligen Loyalitätskonflikt zu verarbeiten und sich trotz aller äusseren Einflüsse bezüglich der Rückführung eine eigene Meinung zu bilden (dazu Andreas Bucher, L'enfant en droit international privé, Basel 2003, S. 168 f., Rz. 487 ff.). Eine völlig unbeeinflusste Willensbildung wird es kaum je geben, und es geht für die Rückführungsbehörde deshalb regelmässig darum, den zwar unter dem Einfluss eines Elternteils entstandenen, aber dennoch beachtlichen Willen von dem unbeachtlichen, allenfalls manipulierten Kindeswillen abzugrenzen (Katja Schweppe, Kindesentführungen und Kindesinteressen, Die Praxis des Haager Übereinkommens in England und Deutschland, Diss. Frankfurt am Main 2001, S. 196).
5.2 In welchem Alter das Kind die für eine möglichst autonome Willensbildung erforderliche Reife erlangt, lässt sich nicht allgemein bestimmen. Vor ein paar Jahren wurde die notwendige Reife in der Regel noch ab dem 14. Altersjahr angenommen (Hans Kuhn, "Ihr Kinderlein bleibet, so bleibet doch all", in: AJP 1997, S. 1102 mit Hinweisen). Andreas Bucher (a.a.O., S. 168, Rz. 486) hält dafür, dass sich ein Mindestalter überhaupt nicht festlegen lasse. Seit einiger Zeit wird in der Rechtsprechung vermehrt auch die Meinung jüngerer Kinder berücksichtigt, frühestens aber ab dem 10. Altersjahr (dazu Carla Schmid, Neuere Entwicklungen im Bereich der internationalen Kindsentführungen, in: AJP 2002, S. 1335 mit Hinweisen). Es ist auf jeden Fall davon auszugehen, dass je näher sich das Kind bei der für die Anwendung des Übereinkommens geltenden Altersgrenze von 16 Jahren (Art. 4 HEntfÜ) befindet, um so eher anzunehmen ist, es verfüge über die nötige Reife, in eigener Verantwortung, möglichst unbeeinflusst vom entführenden Elternteil zu entscheiden, und es sich um so eher rechtfertigt, auf die Meinung des Kindes massgeblich abzustellen (dazu Gerhard Walter/Monique Jametti Greiner/Ivo Schwander, Internationales Privat- und Verfahrensrecht, Texte und Erläuterungen, 2. Band, HEntfÜ [84 E], Ergänzungslieferung Dezember 2000, Rz. 34; Staudinger/Pirrung, Kommentar zum [Deutschen] Bürgerlichen Gesetzbuch, 13. Auflage, Berlin 1994, Vorbem. zu Art. 19 EGBGB, Rz. 685, S. 274). Ist ein Kind - wie hier, wo V._ und W._ im Zeitpunkt ihrer Befragung 10 1⁄2- bzw. 9 1⁄2-jährig waren - vom erwähnten Alter noch verhältnismässig weit entfernt und liegt bezüglich seiner Urteilsfähigkeit ein Grenzfall vor, ist seine Meinung dagegen mit besonderer Zurückhaltung zu würdigen.
5.3 Im Rahmen des Rückführungsverfahrens darf nicht ein Sorgerechtsentscheid getroffen werden; hierfür bleibt - bis zu einer allfälligen rechtskräftigen Abweisung des Rückführungsbegehrens - ausschliesslich das (Familien-)Gericht am Ort des früheren (rechtmässigen) Aufenthalts des Kindes zuständig (vgl. die Art. 16 und 19 HEntfÜ; Kuhn, a.a.O., S. 1093). Mit dem Übereinkommen soll eine spätere Sorgerechtsentscheidung ermöglicht, nicht aber vorweggenommen werden (Zeitschrift für das gesamte Familienrecht [FamRZ] 1998, S. 475).
5.4 Das Obergericht hat festgehalten, V._ und W._ hätten ernsthaft und nachvollziehbar geäussert, nicht nach Spanien zurückgeführt werden zu wollen. Entgegen der Auffassung des Beschwerdeführers bestehe kein Anlass, den Willen der beiden Kinder in Frage zu stellen. Deren Anhörung habe in Anwesenheit einer Fachperson stattgefunden und sei in jeder Hinsicht korrekt gewesen. Die Äusserungen der Kinder hätten auf realem Erleben beruht und ihre ablehnende Haltung erscheine denn auch nicht als aus der Luft gegriffen. Wohl sei nicht zu verkennen, dass die beiden eine solidarische Haltung zur Beschwerdegegnerin einnähmen, doch lasse sich Art. 13 Abs. 2 HEntfÜ kein Hinweis dafür entnehmen, dass die Beweggründe von Bedeutung wären und der Wille des Kindes im Kontext von Art. 13 Abs. 1 lit. a und b HEntfÜ auszulegen wäre. Allerdings heisse dies nicht, dass der Kindeswille nicht kritisch zu hinterfragen wäre, zumal auch Aussagen von Kindern der freien richterlichen Beweiswürdigung unterlägen. Angesichts der Äusserungen von V._ und W._ habe der Amtsgerichtspräsident jedoch ohne Willkür davon ausgehen dürfen, der Ausschlussgrund von Art. 13 Abs. 2 HEntfÜ sei in ihrem Fall gegeben.
5.5 Aus dem Anhörungsprotokoll vom 14. September 2004 geht deutlich hervor, dass die beiden Knaben wünschen, bei der Mutter bleiben zu können und nicht zum Vater zurückkehren zu müssen. V._ erklärte, wenn er ohne Mutter nach Spanien zurückkehren müsste, wäre er allein und nur mit seinen Nachbarn, weil der Vater lange arbeiten müsse. W._ äusserte, Angst zu haben, bei einer Rückkehr nach Spanien einmal auf der Strasse leben zu müssen, da ihnen die finanziellen Mittel fehlen würden; auch die Mutter habe ihm gesagt, dass es sehr schlimm für sie wäre, wenn sie nach Spanien zurückkehren müssten.
Es fällt auf, dass die beiden Kinder sich offensichtlich dazu zu äussern hatten, ob sie lieber bei der Mutter in der Schweiz bleiben oder lieber zum Vater nach Spanien zurückkehren möchten. Die Frage der Rückführung wurde mit andern Worten auf die Frage reduziert, unter wessen Obhut sie lieber leben würden. Wohl ist nicht zu übersehen, dass es das Differenzierungsvermögen eines Kindes übersteigen dürfte, Motive allgemeiner Natur gegen eine Rückkehr ins Herkunftsland von Motiven auseinander zu halten, die gegen eine Rückkehr zum dort lebenden Elternteil sprechen (dazu Schweppe, a.a.O., S. 195). Es dürfte jedoch äusserst fraglich sein, ob V._ und W._ sich anlässlich ihrer Anhörung überhaupt bewusst waren, dass sie sich nicht zur Obhutsfrage, sondern zu einer allfälligen Rückführung nach Spanien zu äussern hatten, wo das zuständige Gericht dann über das Sorgerecht zu befinden haben würde.
Das Obergericht beruft sich auf die Würdigung des von den beiden Knaben geäusserten Willens durch den Amtsgerichtspräsidenten, die es als überzeugend bezeichnet. Der Amtsgerichtspräsident war seinerseits zum Schluss gelangt, den mit V._ und W._ geführten Gesprächen habe nicht entnommen werden können, dass die Knaben von ihrer Mutter auf die Anhörung hin beeinflusst worden wären. Es mag sein, dass die Beschwerdegegnerin die Kinder nicht bewusst auf deren Befragung durch den Richter vorbereitet und auf deren Aussagen nicht unmittelbar eingewirkt hat. Indessen sind bei der Würdigung der Erklärungen von V._ und W._ die gesamten Umstände in Betracht zu ziehen: Die beiden Knaben haben mit der Beschwerdegegnerin fluchtartig Spanien verlassen und bilden seither mit ihr eine ausgeprägte Schicksalsgemeinschaft. In ihrer neuen Umgebung sind die drei mit offenen Armen empfangen worden. V._ und W._ haben ihren Widerstand gegen eine Rückkehr nach Spanien denn auch teilweise mit den aktuellen Lebensverhältnissen und der Beziehung zu den Grosseltern begründet.
Bei Kindern im Alter von V._ und W._ ist es unter den gegebenen Umständen unvorstellbar, dass sie etwas anderes äussern, als bei dem sie betreuenden Elternteil und in ihrer neuen Umgebung bleiben und nicht an den früheren Aufenthaltsort zurückkehren zu wollen. Zu bedenken ist vor allem auch, dass die Beschwerdegegnerin (zumindest) W._ gegenüber erklärt hat, es wäre für sie sehr schlimm, wenn sie nach Spanien zurückkehren müssten. Die Beschwerdegegnerin macht zwar in ihrer Vernehmlassung nicht (mehr) geltend, bei einer Rückkehr nach Spanien mit einer Strafverfolgung rechnen zu müssen, sondern bringt einzig vor, sie würde bei einem Umzug nach Spanien ihre heutige ideale Situation aufgeben. Die Kinder mussten aber angesichts ihrer negativen Einstellung gleichwohl unter dem Eindruck gestanden haben, es sei zumindest nicht ausgeschlossen, dass sie alleine zurückkehren und sich von ihrer Mutter, die für sie zur einzigen näheren Bezugsperson geworden ist, trennen müssten.
5.6 Von einer unbeeinflussten Willensbildung kann unter den dargelegten Umständen nicht die Rede sein. V._ und W._ verfügen offensichtlich nicht über die für die Berücksichtigung ihrer Meinung erforderliche Reife. Zudem ist ihr Wunsch, in der Schweiz zu bleiben, teilweise darauf zurückzuführen, dass sie sich hier eingelebt haben, und insofern deshalb ohnehin unbeachtlich (vgl. oben E. 3.2). Bei dieser Sachlage geht es nicht an, das Rückführungsbegehren gestützt auf Art. 13 Abs. 2 HEntfÜ abzuweisen. Die Vorbringen der Beschwerdegegnerin vermögen - soweit aus novenrechtlicher Sicht überhaupt beachtlich - daran nichts zu ändern.
6. Die staatsrechtliche Beschwerde ist grundsätzlich rein kassatorischer Natur (<ref-ruling> E. 1.2 S. 261 mit Hinweisen). Eine Ausnahme gilt in Fällen, wo die von der Verfassung geforderte Lage nicht schon mit der Aufhebung des angefochtenen kantonalen Entscheids hergestellt wird, sondern dafür eine positive Anordnung nötig ist (<ref-ruling> E. 1.2.1 S. 132 mit Hinweisen). So gibt das Bundesgericht beispielsweise in Rechtsöffnungssachen einem Antrag, mit dem über die Aufhebung des angefochtenen Entscheids hinaus die Erteilung der Rechtsöffnung verlangt wird, unter gewissen Voraussetzungen statt (dazu <ref-ruling> E. 1b S. 257 f.). Diese Grundsätze sind sinngemäss auch auf die vorliegende Staatsvertragsbeschwerde anzuwenden. Das im Rückführungsverfahren geltende Beschleunigungsgebot rechtfertigt es, dass die Anordnung der Rückführung, mit der hier der konventionskonforme Zustand herbeigeführt wird, vom Bundesgericht selbst getroffen wird. Neben der Aufhebung des angefochtenen Entscheids ist daher anzuordnen, dass die Beschwerdegegnerin V._ und W._ bis Ende Mai 2005 nach Spanien zurückbringe.
7. Die staatsrechtliche Beschwerde fällt als bundesrechtliches ausserordentliches Rechtsmittel gegen letztinstanzliche kantonale Rückführungsentscheide entgegen der Auffassung des Beschwerdeführers nicht in den Anwendungsbereich von Art. 26 Abs. 2 HEntfÜ, wonach das Verfahren kostenlos ist. Dem Ausgang des Verfahrens entsprechend ist die Gerichtsgebühr der Beschwerdegegnerin aufzuerlegen (Art. 156 Abs. 1 OG). Diese ist ausserdem zu verpflichten, den Beschwerdeführer für seine Umtriebe im bundesgerichtlichen Verfahren zu entschädigen (Art. 159 Abs. 1 OG). Das Gesuch des Beschwerdeführers, ihm für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege zu gewähren, wird damit insofern gegenstandslos, als er nicht kostenpflichtig ist. Da die Voraussetzungen für die Gewährung des Armenrechts offensichtlich erfüllt sind, ist dem Begehren jedoch insofern stattzugeben, als für den Fall, dass die zugesprochene Parteientschädigung sich nicht einbringen lassen sollte, dem Rechtsvertreter des Beschwerdeführers eine Entschädigung aus der Bundesgerichtskasse zuzusprechen ist (Art. 152 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird gutgeheissen und der Entscheid des Obergerichts (II. Kammer) des Kantons Luzern vom 11. November 2004 aufgehoben.
2. Die Beschwerdegegnerin hat die beiden Kinder V._ und W._ bis Ende Mai 2005 nach Spanien zurückzubringen.
3. Die Gerichtsgebühr von Fr. 2'000.-- wird der Beschwerdegegnerin auferlegt.
4. Die Beschwerdegegnerin wird verpflichtet, den Beschwerdeführer für seine Umtriebe im bundesgerichtlichen Verfahren mit Fr. 2'000.-- zu entschädigen.
5. Soweit das Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege nicht gegenstandslos geworden ist, wird es gutgeheissen, und es wird dem Beschwerdeführer in der Person von Rechtsanwalt lic. iur. Thomas Baumeler ein unentgeltlicher Rechtsbeistand beigegeben; im Falle der Uneinbringlichkeit der Parteientschädigung wird diesem aus der Bundesgerichtskasse eine Entschädigung von Fr. 1'500.-- ausgerichtet.
6. Dieses Urteil wird den Parteien und dem Obergericht (II. Kammer) des Kantons Luzern schriftlich mitgeteilt.
Lausanne, 22. März 2005
Im Namen der II. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: