Sachverhalt: A. Die im Jahre 1997 geborene A.X._ ist die Tochter von B.X._ und C.Y._, welche ab Juli 1997 bis Oktober 1999 im Konkubinat lebten. Nach der Trennung sah sich B.X._ nicht in der Lage, das Kind zu betreuen. Die Eltern ersuchten daher die Vormundschaftsbehörde darum, die elterliche Sorge auf den Vater zu übertragen. Mit Beschluss vom 15. November 1999 entzog der Gemeinderat G._ als Vormundschaftsbehörde B.X._ (gestützt auf Art. 312 Ziff. 1 ZGB) die elterliche Gewalt über A.X._ und stellte das Kind (gestützt auf Art. 298 Abs. 2 ZGB) unter die elterliche Gewalt von C.Y._. B. Am 4. Februar 2003 stellte A.X._ durch ihren gesetzlichen Vertreter bei der Direktion der Justiz und des Innern des Kantons Zürich das Begehren, es sei ihr gestützt auf Art. 30 Abs. 1 ZGB die Änderung des bisherigen Familiennamens "X._" in "Y._" zu bewilligen. Mit unbegründeter Verfügung vom 30. Mai 2005 wurde dem Gesuch um Namensänderung nicht entsprochen. Auf Einsprache hin wies die kantonale Direktion der Justiz und des Innern mit begründeter Verfügung vom 15. August 2005 das Gesuch von A.X._ ab. Hiergegen erhob A.X._ Rekurs, welchen das Obergericht des Kantons Zürich, II. Zivilkammer, mit Beschluss vom 12. Dezember 2005 abwies. C. A.X._ führt mit Eingabe vom 16. Januar 2006 eidgenössische Berufung und beantragt dem Bundesgericht, der Beschluss (Ziff. 2-5) des Obergerichts sei aufzuheben und es sei ihr die Änderung des Familiennamens von "X._" in "Y._" zu bewilligen. Das Obergericht hat auf Gegenbemerkungen verzichtet. B.X._ beantragt die Abweisung der Berufung und ersucht um unentgeltliche Rechtspflege.