Sachverhalt:
A. A.a X._ (italienischer Staatsangehöriger) und Y._ (schweizerische Staatsangehörige) sind die nicht miteinander verheirateten Eltern der 2007 in A._ geborenen Tochter B._. Die Familie wohnte zunächst in C._ bzw. in D._ und zog schliesslich am 1. November 2008 nach Irland. Im Frühling 2009 erfolgte die Trennung; X._ zog aus der gemeinsamen Wohnung aus, blieb aber in Irland wohnhaft.
A.b Anfang August 2009 reiste Y._ erstmals in die Schweiz und meldete sich am 10. August 2009 bei der Einwohnergemeinde D._ an. In der Folge kehrte sie nach Irland zurück, um den endgültigen Umzug in die Schweiz zu organisieren.
A.c X._ leitete in Irland ein Verfahren betreffend Zuteilung der gemeinsamen elterlichen Sorge ein. Y._ leistete der ordnungsgemässen Vorladung zur Verhandlung vom 3. September 2009 keine Folge, sondern reiste am frühen Morgen des Verhandlungstages zusammen mit dem Kind in die Schweiz. Gleichentags setzte der District Court of E._ X._ zusammen mit Y._ als "joint guardian" (Sorgeberechtigten) ein und entschied, dass die Tochter B._ den Gerichtsbezirk ohne Einwilligung des Gerichts nicht verlassen dürfe.
B. Mit Eingabe vom 28. Oktober 2009 ersuchte X._ beim Kantonsgericht von Graubünden gestützt auf das Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführung um Rückführung seiner Tochter nach Irland. Das angerufene Gericht wies das Gesuch mit Urteil vom 7. Dezember 2009 ab, überband die Kosten des Verfahrens dem Kanton Graubünden und verpflichtete X._, Y._ für das Verfahren ausseramtlich mit Fr. 4'000.-- einschliesslich Mehrwertsteuer zu entschädigen.
C. X._ hat gegen das seinem Rechtsbeistand am 16. Dezember 2009 zugestellte Urteil des Kantonsgerichts von Graubünden mit einer am 11. Januar 2010 der Post übergebenen Eingabe Beschwerde in Zivilsachen eingereicht. Er beantragt die Aufhebung des kantonsgerichtlichen Urteils und die Anordnung der Rückführung des Kindes nach Irland; ferner sei der Entscheid mit Vollstreckungsmassnahmen zu verbinden. Für die Dauer des Verfahrens seien die vom Kantonsgericht Graubünden mit Verfügung vom 19. November 2009 angeordneten vorsorglichen Massnahmen weiterzuführen: all dies unter gesetzlicher Kosten- und Entschädigungsfolge für die Verfahren vor Vorinstanz und das vorliegende Verfahren. In der Beschwerdeschrift beantragt er zudem, Ziff. 3 des Urteilsdispositivs des angefochtenen Entscheids sei unabhängig vom Ausgang des Verfahrens dahingehend zu ändern, dass er der Beschwerdegegnerin keine ausseramtliche Entschädigung zu bezahlen habe.
Y._ beantragt in ihrer Vernehmlassung vom 25. Januar 2010, unter Kosten- und Entschädigungsfolge, die Beschwerde sei abzuweisen. Eventuell seien bei den irischen Gerichten der Stand der Verfahren und der Inhalt der aktuell rechtskräftigen Entscheide in Erfahrung zu bringen und es sei den Parteien eine weitere Frist zur Vernehmlassung zu gewähren. Mit Bezug auf die vorsorglichen Massnahmen für die Dauer des bundesgerichtlichen Verfahrens stellt sie den Antrag, dem Beschwerdeführer sei in Abänderung der vom Kantonsgericht angeordneten Massnahmen neu ein Besuchsrecht alle 14 Tage je an einem Freitag ab 14.30 bis 18.30 Uhr zu gewähren, wobei er wie bis anhin mit dem Kind den Kanton Graubünden nicht verlassen dürfe und zur Sicherstellung seinen Pass beim zuständigen Polizeiposten zu deponieren habe. Schliesslich ersucht sie um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren.
D. Mit Verfügung vom 26. Januar 2010 hat der Instruktionsrichter hinsichtlich der vorsorglichen Massnahmen dem Antrag des Beschwerdeführers entsprochen.

Erwägungen:
1. 1.1 Beim Verfahren betreffend Rückführung eines Kindes nach dem Haager Übereinkommen vom 25. Oktober 1980 über die zivilrechtlichen Aspekte internationaler Kindesentführung (HKÜ; SR 0.211.230.02) geht es um die Regelung der Rechtshilfe zwischen den Vertragsstaaten, mithin um eine Angelegenheit öffentlich-rechtlicher Natur, die in unmittelbarem Zusammenhang mit der Respektierung und Durchsetzung ausländischen Zivilrechts steht (Art. 72 Abs. 2 lit. b Ziff. 1 BGG; <ref-ruling> E. 1.2 mit Hinweisen). Das Urteil des Kantonsgerichts von Graubünden als oberen kantonalen Gerichts gilt als letztinstanzlicher kantonaler Entscheid im Sinn von Art. 75 Abs. 1 und Art. 90 BGG (Art. 7 Abs. 1 des Bundesgesetzes über internationale Kindesentführung und die Haager Übereinkommen zum Schutz von Kindern und Erwachsenen [BG-KKE; SR 211.222.32]). Die Beschwerde in Zivilsachen ist daher gegeben. Der angefochtene Entscheid ist dem Beschwerdeführer am 16. Dezember 2009 zugestellt worden, womit die zehntägige Beschwerdefrist (<ref-law>), die während der Gerichtsferien vom 18. Dezember 2009 bis und mit 2. Januar 2010 stillstand (<ref-law>), am Montag 11. Januar 2010 abgelaufen ist. Auf die rechtzeitig eingereichte Beschwerde ist somit einzutreten.
1.2 Geltend gemacht werden kann insbesondere die Verletzung von Völkerrecht, dessen Anwendung das Bundesgericht frei prüft (Art. 95 lit. b i.V.m. <ref-law>). Demgegenüber können Sachverhaltsfeststellungen nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich (<ref-ruling> E. 1.2.2 S. 252) und für den Ausgang des Verfahrens entscheidend sind (<ref-law>).
1.3 Gegenstand des vorliegenden Verfahrens ist einzig ein Antrag des Beschwerdeführers auf Rückführung des Kindes gestützt auf das Übereinkommen. Der Eventualantrag der Beschwerdegegnerin und das Begehren um Ansetzung einer neuen Frist zur Vernehmlassung beziehen sich nicht auf den Streitgegenstand. Darauf ist nicht einzutreten.
2. Strittig ist zunächst, ob die Beschwerdegegnerin das gemeinsame Kind der Parteien in Verletzung des vorgenannten Abkommens in die Schweiz verbracht hat. Das HKÜ zielt auf sofortige Rückgabe widerrechtlich in einen Vertragsstaat verbrachter oder dort zurückgehaltener Kinder (Art. 1 lit. a). Als widerrechtlich gilt das Verbringen oder Zurückhalten eines Kindes, wenn dadurch das Sorgerecht verletzt wird, das einer Person allein oder gemeinsam nach den Regeln des Staates zusteht, in dem das Kind unmittelbar vor dem Verbringen oder Zurückhalten seinen gewöhnlichen Aufenthalt hatte (Art. 3 Abs. 1 lit. a).
2. Strittig ist zunächst, ob die Beschwerdegegnerin das gemeinsame Kind der Parteien in Verletzung des vorgenannten Abkommens in die Schweiz verbracht hat. Das HKÜ zielt auf sofortige Rückgabe widerrechtlich in einen Vertragsstaat verbrachter oder dort zurückgehaltener Kinder (Art. 1 lit. a). Als widerrechtlich gilt das Verbringen oder Zurückhalten eines Kindes, wenn dadurch das Sorgerecht verletzt wird, das einer Person allein oder gemeinsam nach den Regeln des Staates zusteht, in dem das Kind unmittelbar vor dem Verbringen oder Zurückhalten seinen gewöhnlichen Aufenthalt hatte (Art. 3 Abs. 1 lit. a).
2.1 2.1.1 Nach Auffassung des Kantonsgerichts hatte das Kind unmittelbar vor der Ausreise aus Irland seinen gewöhnlichen Aufenthalt in der Schweiz. Die Vorinstanz hat insbesondere erwogen, nach irischem Recht gelte die mit dem Beschwerdeführer nicht verheiratete Beschwerdegegnerin als alleinige Inhaberin der elterlichen Sorge, wenn keine anderslautende Vereinbarung oder ein anderslautender Gerichtsentscheid bestehe. Die Beschwerdegegnerin sei ihren Angaben anlässlich der Verhandlung vom 7. Dezember 2009 zufolge am 31. Juli 2009 zusammen mit ihrer Tochter für zwei Wochen in die Schweiz gereist, um ihre Rückkehr in dieses Land zu organisieren. Am 10. August 2009 habe sie sich bei der Einwohnerkontrolle von D._ angemeldet. Da sie sich mit der Absicht längeren Verbleibens in dieser Ortschaft niedergelassen habe, sei dort bereits zu diesem Zeitpunkt der gewöhnliche Aufenthalt begründet worden. Daran ändere nichts, dass die Beschwerdegegnerin danach kurzzeitig nach Irland zurückgekehrt sei, um den dortigen Aufenthalt abzuschliessen und ihre persönlichen Gegenstände in die Schweiz zu versenden, habe es sich doch lediglich um eine Unterbrechung der Anwesenheit in der Schweiz gehandelt. Aufgrund der Aussagen des Beschwerdeführers stehe fest, dass dieser Anfang August 2009 zwar erste Kontakte mit seiner Rechtsvertretung ausgenommen habe, zu diesem Zeitpunkt aber in Irland noch kein Verfahren betreffend das Sorgerecht hängig gewesen sei. Die Beschwerdegegnerin habe damit am 31. Juli 2009 als alleinige Inhaberin der elterlichen Sorge den Aufenthalt des Kindes bestimmen können.
2.1.2 Der Beschwerdeführer macht geltend, die vorgenannten Ausführungen der Vorinstanz beruhten zum Teil auf einer willkürlichen Feststellung des Sachverhalts und liessen insgesamt nicht auf eine Begründung des gewöhnlichen Aufenthalts in der Schweiz schliessen.
2.1.3 Es ist in der Tat fraglich, ob die Beschwerdegegnerin und das Kind bereits mit der Einreise in die Schweiz (31. Juli 2009) und mit der im August 2009 erfolgten Anmeldung bei der Einwohnerkontrolle von D._ einen neuen, für das vorliegende Verfahren massgeblichen gewöhnlichen Aufenthalt in der Schweiz begründet haben. Diese Frage kann indes offenbleiben, zumal der letztinstanzliche kantonale Entscheid auch bei Annahme des gewöhnlichen Aufenthaltes in Irland nicht völkerrechtswidrig ist:
2.1.3 Es ist in der Tat fraglich, ob die Beschwerdegegnerin und das Kind bereits mit der Einreise in die Schweiz (31. Juli 2009) und mit der im August 2009 erfolgten Anmeldung bei der Einwohnerkontrolle von D._ einen neuen, für das vorliegende Verfahren massgeblichen gewöhnlichen Aufenthalt in der Schweiz begründet haben. Diese Frage kann indes offenbleiben, zumal der letztinstanzliche kantonale Entscheid auch bei Annahme des gewöhnlichen Aufenthaltes in Irland nicht völkerrechtswidrig ist:
2.2 2.2.1 Zur Begründung der Widerrechtlichkeit macht der Beschwerdeführer im Wesentlichen geltend, die Beschwerdegegnerin habe unbestrittenermassen am 31. August bzw. 1. September 2009 von der Vorladung des District Court of E._ zur Verhandlung vom 3. September 2009 Kenntnis erhalten und sei demnach am 3. September 2009 nicht mehr alleinige Inhaberin des Sorgerechts gewesen, da der mit der Sache befasste District Court von E._ vielmehr aufgrund des "Ward of Court" selbst Inhaber des Sorgerechts geworden sei. Dieser sog. "Ward of Court" sei hinzunehmen, auch wenn er dem schweizerischen Rechtssystem fremd sei.
Die Beschwerdegegnerin weist im Wesentlichen darauf hin, nach irischem Recht sei sie unbestrittenermassen alleinige Inhaberin des Sorgerechts; der Beschwerdeführer behaupte zwar, belege aber nicht, dass sich die Sorgerechtslage bereits mit der Vorladung geändert habe, indem das Gericht bereits mit der Vorladung ein virtuelles Sorgerecht übernommen hätte.
2.2.2 Nach dem Wortlaut von Art. 3 lit. a HKÜ ist das Verbringen des Kindes in die Schweiz nur dann widerrechtlich, wenn das Sorgerecht verletzt wurde, das einer Person oder Behörde unmittelbar vor dem Verbringen des Kindes zustand. Massgeblich ist also die Sorgerechtslage, wie sie beim Verbringen bestanden hat; dieser Status quo ante soll wiederhergestellt werden, weshalb ein Verbringen kurz vor einer erwarteten Entscheidung keinen Rückführungsanspruch zu begründen vermag und insbesondere auch ein nachträgliches Missbilligen durch einen Gerichtsentscheid nicht von Art. 3 HKÜ erfasst wird (Urteil 5A_713/2007 vom 28. Februar 2008, FamPra.ch 2008 S. 703 E. 3 S. 705).
2.2.3 Nach der bundesgerichtlichen Rechtsprechung kann das Institut des "Ward of Court" zwar eine geschützte Sorgerechtsposition im Sinn von Art. 3 HKÜ begründen; das betreffende Sorgerecht muss aber im Zeitpunkt des Verbringens des Kindes bestanden haben und überdies tatsächlich ausgeübt worden sein (Urteil 5A_713/2007 vom 28. Februar 2008, FamPra.ch 2008 S. 703 E. 3 S. 705 f.). Der Beschwerdeführer hat im kantonalen Verfahren erst im Rahmen des Parteivortrags auf diese Rechtsfigur hingewiesen und hat insbesondere nicht behauptet, geschweige denn belegt, dass er vor den irischen Gerichten die Anordnung des "Ward of Court" verlangt hat und diesem Begehren auch entsprochen worden ist. Solches ergibt sich denn auch nicht aus den zu den Akten gegebenen Kopien der irischen Entscheide. Damit ist nicht erstellt, dass im Zeitpunkt der Ausreise in die Schweiz ein "Ward of Court" bestanden hat mit der Folge, dass die Ausreise in die Schweiz deswegen rechtswidrig im Sinn des Abkommens war. Sodann wird auch nicht belegt, dass der District Court of E._ vor seinem Entscheid vom 3. September 2009 der Mutter die Ausreise mit dem Kind untersagt hat.
2.2.4 Angesichts der nicht bewiesenen Anordnung des "Ward of Court" ist davon auszugehen, dass die ursprüngliche Rechtslage (alleiniges Sorgerecht der Beschwerdegegnerin) erst durch den Entscheid des District Court of E._ geändert worden ist, der den Beschwerdeführer zusammen mit der Beschwerdegegnerin als "joint guardian" (Sorgeberechtigten) eingesetzt hat. Kurz vor diesem Entscheid, nämlich am Morgen des 3. September 2009, zu einem Zeitpunkt, als ihr alleiniges Sorgerecht noch bestand, hat die Beschwerdegegnerin das Land mit der gemeinsamen Tochter verlassen. Ein widerrechtliches Verhalten der Beschwerdeführerin im Sinn des Abkommens liegt nicht vor.
3. 3.1 Das Kantonsgericht hat den Beschwerdeführer unter Berücksichtigung des Urteils 5A_582/2007 vom 4. Dezember 2007 verpflichtet, die Beschwerdegegnerin für das Verfahren ausseramtlich mit Fr. 4'000.-- zu entschädigen. Der Beschwerdeführer macht geltend, nach <ref-law> sei das Verfahren kostenlos, soweit nicht das sogenannte Reziprozitätsprinzip zur Anwendung gelange. Mangels Vorbehalts vonseiten Irlands könnten ihm weder Gerichtskosten noch Kosten für den Anwalt auferlegt werden, welche Regel sich auch auf die Parteikosten der Gegenpartei beziehe. Das Bundesgericht habe denn auch in Urteil 5A_721/2009 vom 7. Dezember 2009 einen Beschwerdeführer trotz Abweisung der Beschwerde nicht zu ausseramtlichen Entschädigungen an die Beschwerdegegnerin verurteilt, sondern beide Parteivertreter zulasten des Bundes entschädigt. Die Beschwerdegegnerin schliesst sich im Wesentlichen der vorinstanzlichen Auffassung an.
3.2 Wie der Beschwerdeführer zu Recht bemerkt, ist Art. 26 HKÜ auf die Kosten des Vermittlungsverfahrens und der Mediation sowie der Gerichts- und Vollstreckungsverfahren in den Kantonen und auf Bundesebene anwendbar (<ref-law>). Der Hinweis auf das Urteil 5A_721/2009 verfängt indes nicht, wurde doch im besagten Fall beiden Parteien die unentgeltliche Rechtspflege und Verbeiständung gewährt. Aber auch das vom Kantonsgericht zitierte Urteil 5A_582/2007 vermag die angefochtene Kostenverlegung nicht zu rechtfertigen: In diesem Fall hatte der Vater (Antragsteller) bei den eidgenössischen Behörden um Rückführung seiner Kinder nach Frankreich ersucht; das Bundesgericht hatte die von der Mutter gegen die Anordnung der Rückführung eingereichte Beschwerde abgewiesen und dem Begehren des Vaters entsprochen. Bei einer Anordnung der Rückführung können die Gerichte gestützt auf Art. 26 Abs. 4 HKÜ der Person, die das Kind verbracht oder zurückgehalten hat, die Erstattung der dem Antragsteller selbst oder für seine Rechnung entstandenen notwendigen Kosten auferlegen; dazu gehören insbesondere auch die Kosten der Rechtsvertretung. Wird aber, wie im konkreten Fall, dem Rückführungsantrag nicht entsprochen, so erfolgt die Kostenverlegung nicht nach Art. 26 Abs. 4 HKÜ, sondern nach Art. 26 Abs. 2 i.V.m. Abs. 3 HKÜ.
3.3 Artikel 26 Abs. 2 und 3 HKÜ lauten in ihrem Originalwortlaut wie folgt:
L'Autorité centrale et les autres services publics des Etats contractants n'imposeront aucun frais en relation avec les demandes introduites en application de la Convention. Notamment, ils ne peuvent réclamer du demandeur le paiement des frais et dépens du procès ou, éventuellement, des frais entraînés par la participation d'un avocat. Cependant, ils peuvent demander le paiement des dépenses causées ou qui seraient causées par les opérations liées au retour de l'enfant.
Toutefois, un Etat contractant pourra, en faisant la réserve prévue à l'art. 42, déclarer qu'il n'est tenu au paiement des frais visés à l'alinéa précédent, liés à la participation d'un avocat ou d'un conseiller juridique, ou aux frais de justice, que dans la mesure où ces coûts peuvent être couverts par son système d'assistance judiciaire et juridique.
3.4 Aufgrund des Wortlautes der Originalfassung von Art. 26 Abs. 2 HKÜ ergibt sich einerseits, dass die Zentralbehörde bzw. die anderen Behörden für die nach diesem Übereinkommen gestellten Anträge keine Kosten (frais) erheben dürfen (Satz 1). Anderseits wird in Satz 2 beispielhaft (notamment) präzisiert, dass dem Antragsteller, hier also dem Beschwerdeführer, im Zusammenhang mit einem gestützt auf das HKÜ eingeleiteten Verfahren weder Gerichts- noch Parteikosten des Verfahrens (le paiement des frais et dépens du procès) auferlegt werden dürfen.
3.5 Gemäss dem erläuternden Bericht zum HKÜ wurde in Absatz 2 von Art. 26 einer der umstrittensten Punkte der vierzehnten Sitzung der Haager Konferenz für internationales Privatrecht angesprochen, in dem schliesslich mit dem in Absatz 3 des Artikels enthaltenen Kompromiss eine Lösung gefunden werden konnte. Die Kontroverse zwischen den Delegationen, die dem Antragsteller die umfassende Kostenlosigkeit bei der Anwendung des Übereinkommens zusichern wollten, und jenen Delegationen, welche die gegenteilige Auffassung des Vorentwurfs vertraten, habe in der Tat nur mit einem Kompromiss zugunsten der Letzteren gelöst werden können (Elisa Pérez-Vera, Erläuternder Bericht zum HKÜ, in: Conférence de la Haye de droit international privé, Actes et documents de la Quatorzième session, tome III, S. 425/468 Ziff. 135).
3.6 Der Wortlaut von Art. 26 Abs. 2 HKÜ und die Ausführungen des erläuternden Berichts legen nahe, dass dem Antragsteller in den die Konvention betreffenden Verfahren weder Gerichts- noch Parteikosten auferlegt werden können, es sei denn, einer der beteiligten Staaten habe den Vorbehalt gestützt auf Art. 26 Abs. 3 HKÜ erklärt. Im vorliegenden Fall hat sich weder Irland noch die Schweiz des Vorbehaltes bedient, weshalb zugunsten des Beschwerdeführers von einer umfassenden Kostenlosigkeit des Verfahrens auszugehen ist. Diesem Grundsatz hat das Kantonsgericht nicht Rechnung getragen, indem es den Beschwerdeführer (Antragsteller) verpflichtete, die Beschwerdegegnerin ausseramtlich mit Fr. 4'000.-- zu entschädigen.
4. Damit ist die Beschwerde teilweise gutzuheissen und Ziffer 3 des angefochtenen Urteils aufzuheben. Die Sache ist zur Behandlung des Gesuchs der Beschwerdegegnerin um unentgeltliche Rechtspflege für das kantonale Verfahren an die Vorinstanz zurückzuweisen. Im Übrigen wird die Beschwerde abgewiesen.
5. Für das bundesgerichtliche Verfahren sind keine Gerichtskosten zu erheben (Art. 26 Abs. 2 HKÜ). Dem Beschwerdeführer wird für das bundesgerichtliche Verfahren eine Entschädigung aus der Bundesgerichtskasse entrichtet.
6. Das Gesuch der offensichtlich bedürftigen Beschwerdegegnerin um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren wird gutgeheissen. Ihr wird ein amtlicher Rechtsbeistand bestellt, welcher für seine Bemühungen im bundesgerichtlichen Verfahren aus der Bundesgerichtskasse zu entschädigen ist (Art. 64 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen; Ziffer 3 des Urteils des Kantonsgerichts von Graubünden vom 7. Dezember 2009 wird aufgehoben und die Sache zur Behandlung des Gesuchs der Beschwerdegegnerin um unentgeltliche Rechtspflege für das kantonale Verfahren an die Vorinstanz zurückgewiesen.
2. Das Gesuch der Beschwerdegegnerin um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren wird gutgeheissen. Ihr wird Rechtsanwalt Dr. Heinz Lüscher, Weisse Gasse 14, 4001 Basel, als amtlicher Rechtsbeistand bestellt.
3. Es werden keine Kosten erhoben.
4. Dem Beschwerdeführer und Rechtsanwalt Lüscher wird für das bundesgerichtliche Verfahren je eine Entschädigung von Fr. 2'000.-- aus der Bundesgerichtskasse entrichtet.
5. Dieses Urteil wird den Parteien, der Kantonspolizei Graubünden, dem Bundesamt für Justiz, Zentralbehörde zur Behandlung internationaler Kindesentführungen, z.H. Frau Jenny Hutter, und dem Kantonsgericht von Graubünden, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 2. Februar 2010
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Zbinden