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. 