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 Art. 137 ZGB 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.