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 <ref-law>) die elterliche Gewalt über A.X._ und stellte das Kind (gestützt auf <ref-law>) 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 <ref-law> 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.

Das Bundesgericht zieht in Erwägung:
1. Gegen den obergerichtlichen Beschluss, mit dem die verlangte Namensänderung kantonal letztinstanzlich verweigert worden ist, kann die eidgenössische Berufung ergriffen werden (Art. 44 lit. a, Art. 48 Abs. 1 OG).
2. Die Regierung des Wohnsitzkantons kann einer Person die Änderung des Namens bewilligen, wenn wichtige Gründe vorliegen (<ref-law>). Ob im einzelnen Fall ein Grund für eine Namensänderung vorliegt, ist eine Ermessensfrage, die von der zuständigen Behörde nach Recht und Billigkeit zu beantworten ist (vgl. <ref-law>). Ermessensentscheide dieser Art überprüft das Bundesgericht an sich frei; es übt dabei allerdings Zurückhaltung und greift nur ein, wenn die kantonale Instanz von dem ihr zustehenden Ermessen einen falschen Gebrauch gemacht hat, d.h. wenn sie grundlos von in Lehre und Rechtsprechung anerkannten Grundsätzen abgegangen ist, wenn sie Umstände berücksichtigt hat, die keine Rolle hätten spielen dürfen, oder wenn sie umgekehrt rechtserhebliche Umstände ausser Acht gelassen hat (vgl. <ref-ruling> E. 2a S. 402).
3. 3.1 Das Obergericht hat im Wesentlichen festgehalten, der Umstand, dass die Berufungsklägerin unter die elterliche Sorge des mit der Mutter nicht verheirateten Vaters gestellt worden sei, gebe keinen Anspruch auf Namensänderung und stelle keinen wichtigen Grund im Sinne von <ref-law> dar, um die Änderung des von ihrer Mutter erworbenen Namens in jenen des leiblichen Vaters zu bewilligen. Die gegenteilige Auffassung der Berufungsklägerin werde durch den Wortlaut von <ref-law> nicht gestützt. Im Übrigen hat das Obergericht erwogen, dass weiter kein wichtiger Grund vorliege, um die anbegehrte Namensänderung zu bewilligen, denn es würden keine ernsthaften sozialen Nachteile für die 8-jährige Berufungsklägerin dargetan, welche durch die Führung des Namens der Mutter bedingt wären. Das Obergericht ist zum Schluss gelangt, die Verweigerung der Namensänderung sei nicht zu beanstanden.
3.2 Die Berufungsklägerin macht eine Verletzung von <ref-law> geltend, weil das Obergericht die Tatsache, dass sie als aussereheliches Kind unter der elterlichen Sorge des Vaters aufwachse, in Widerspruch zu Wortlaut und Zweck der betreffenden Norm nicht als wichtigen Grund zur Namensänderung erachtet habe. Sodann sei unter Hinweis auf <ref-law> mit einer verfassungskonformen Auslegung nicht vereinbar, wenn ein Kind einer unverheirateten Mutter von Gesetzes wegen in deren elterlichen Sorge stehe und deren Namen erhalte, hingegen ein Kind unverheirateter Eltern, welches unter der elterlichen Sorge des Vaters aufwachse, dessen Namen nur bei Nachweis erheblicher und konkreter sozialer Nachteile annehmen dürfe. Die Berufungsklägerin sei wegen der frühen Trennung von der Mutter labil; mit der Namensänderung könne sie sich auch über den Namen in der Familie des Vaters geborgen fühlen. Daher lägen ernsthafte soziale Nachteile vor, um die Namensänderung zu bewilligen.
4. Nach den kantonalen Sachverhaltsfeststellungen wurde die elterliche Sorge für die Berufungsklägerin im Jahre 1999 gestützt auf <ref-law> dem Vater übertragen. Es steht fest, dass die Eltern der Berufungsklägerin nie verheiratet waren und heute nicht zusammenleben, sondern sich diese in der Zwischenzeit jeweils mit anderen Partnern verheiratet haben. Aus dem angefochtenen Beschluss geht hervor, dass die Berufungsklägerin seit dem Jahre 1999 bzw. dem zweiten Lebensjahr nicht mehr zusammen mit ihrer Mutter, sondern bei ihrem Vater aufwächst. Strittig ist, ob der Umstand, dass die Berufungsklägerin in die elterliche Sorge des mit der Mutter nicht verheirateten Vaters gegeben worden ist und bei diesem aufwächst, in Anwendung von <ref-law> einen wichtigen Grund im Sinne von <ref-law> darstellt, um die Änderung des von ihrer Mutter erworbenen Namens in jenen des Vaters zu bewilligen.
4.1 Gemäss <ref-law> erhält das Kind nicht verheirateter Eltern den Familiennamen der Mutter. Zur Korrektur dieses Namenserwerbs muss ein wichtiger Grund im Sinne von <ref-law> vorliegen. Nach der Rechtsprechung liegt ein solcher vor, wenn der nach <ref-law> übertragene Name seinem Träger konkrete und ernsthafte soziale Nachteile verursacht (<ref-ruling> E. 3a S. 3, E. 5 S. 5 mit Hinweisen). Zu prüfen ist, ob diese Voraussetzung - wie das Obergericht angenommen hat - auch dann nachzuweisen ist, wenn ein aussereheliches Kind gemäss <ref-law> in der elterlichen Sorge des Vaters aufwächst.
4.2 <ref-law> lautet wie folgt: "Erwirbt das Kind unverheirateter Eltern durch Namensänderung den Familiennamen des Vaters, weil es unter seiner elterlichen Sorge aufwächst, so erhält es das Kantons- und Gemeindebürgerrecht des Vaters." Diese Bestimmung bezieht sich nach dem Wortlaut auf den Bürgerrechtserwerb im Fall der bewilligten Namensänderung. Indirekt anerkennt der Gesetzgeber aber, dass ein nach <ref-law> wichtiger Grund vorliegt, wenn das aussereheliche Kind in die elterliche Sorge des Vaters gegeben wird und bei ihm aufwächst. Ansonsten hätte das Gesetz es bei der Regelung bewenden lassen können, dass das Kind das Bürgerrecht des Vaters erwirbt, wenn es durch Namensänderung dessen Namen erwirbt. Läge nicht im Aufwachsen des ausserehelichen Kindes unter der elterlichen Sorge des Vaters von Gesetzes wegen ein wichtiger Grund für eine Namensänderung bzw. bedürfte es in einem solchen Fall eines zusätzlichen (anderen) wichtigen Grundes, hätte der Satzeinschub "weil es unter seiner elterlichen Sorge aufwächst" ("... élevé sous l'autorité du père et reçoit par conséquent ...", "... essendo allevato sotto l'autorità del padre ...") keinen Sinn.
4.3 Der Einwand der Beschwerdegegnerin, die Bestimmung stehe in keinem Zusammenhang mit dem Namensrecht, geht fehl. Die Entstehungsgeschichte der Bestimmung (vgl. Rolf Häfliger, Die Namensänderung nach <ref-law>, Diss. Zürich 1996, S. 252 f.) zeigt vielmehr das Gegenteil. Der Entwurf des Bundesrates zum neuen Kindesrecht enthielt unter Art. 30 Abs. 2 einen nicht abschliessenden Katalog von wichtigen Gründen (BBl 1974 II 92 ff., S. 133). Ein wichtiger Grund lag vor (Ziff. 3), "wenn der unmündige Gesuchsteller einen andern Familiennamen trägt als der Elternteil, unter dessen elterlicher Gewalt oder Obhut er aufwächst." <ref-law> nimmt auf diesen Wortlaut Bezug (BBl 1974 II 50 f.), wobei die im Entwurf vorgesehene blosse "Obhut" als alternative Voraussetzung neben der elterlichen Gewalt gestrichen wurde (AB 1976 S S. 85). Am Zusammenhang mit dem Namensrecht ändert nichts, dass sich das Parlament schliesslich dagegen aussprach, die "wichtigen Gründe" in <ref-law> zu kodifizieren (dazu <ref-ruling> E. 2 S. 178).
4.4 Weiter ist nicht ersichtlich, dass die Annahme, für ein aussereheliches Kind, das beim Vater als Träger der elterlichen Sorge aufwächst (<ref-law>), liege ein wichtiger Grund zur Namensänderung vor, dem Sinn und Zweck von <ref-law> zuwiderlaufen soll.
4.4.1 Der Schluss, dass der in <ref-law> genannte Umstand als wichtiger Grund anerkannt wird, ergibt sich aus dem vom Gesetz hergestellten Zusammenhang zwischen elterlicher Sorge und Namensgebung. Die Regel des <ref-law>, wonach das Kind unverheirateter Eltern von Gesetzes wegen den Namen der Mutter erhält, beruht auf dem Gedanken, dass ein solches Kind normalerweise bei der Mutter aufwächst, zu der es engere Beziehungen als zum Vater hat (<ref-ruling> E. 6 S. 252). Wohl ist nicht Voraussetzung, dass der Mutter die elterliche Sorge zusteht, damit das Kind unverheirateter Eltern den Familiennamen der Mutter gemäss <ref-law> erwirbt (Hegnauer, Berner Kommentar, N. 30 zu <ref-law>). Im Allgemeinen steht aber die elterliche Sorge der Mutter zu (<ref-law>), sofern nicht eine gemeinsame elterliche Sorge vereinbart wird (<ref-law>). Nur wenn die Mutter unmündig, entmündigt oder gestorben oder ihr die elterliche Sorge entzogen ist, kann die elterliche Sorge bei gegebenen Voraussetzungen (Kindeswohl) dem Vater übertragen werden (<ref-law>). Nach der Meinung von Hegnauer (a.a.O., N. 82 zu <ref-law>) setzt diese Übertragung der elterlichen Sorge an den Vater gemäss <ref-law> praktisch voraus, dass das aussereheliche Kind dauernd nicht bei der Mutter aufwachsen wird. Der gesetzlichen Wertung, wonach das Kind unverheirateter Eltern den Namen der Mutter trägt und im Allgemeinen unter der elterlichen Sorge der Mutter steht, entspricht es, dass es sich ebenso verhält, wenn der Vater das Sorgerecht für das bei ihm aufwachsende Kind trägt. In Anbetracht dieser besonderen Beziehung zum leiblichen Vater hat der Gesetzgeber erhebliche Nachteile für das aussereheliche Kind gesehen, wenn es gemäss <ref-law> den Namen der Mutter tragen muss. Deshalb soll dem Kind - zur Erleichterung der Integration in die Familie - offen stehen, durch Namensänderung (<ref-law>) den Namen des leiblichen Vaters zu erwerben, bei dem es aufwächst.
4.4.2 Im Übrigen wird in <ref-ruling> E. 6 S. 252 implizit angenommen, dass es sich beim Umstand, dass ein aussereheliches Kind beim Vater als Träger der elterlichen Sorge aufwächst, um einen wichtigen Grund im Sinne von <ref-law> handelt: Das Bundesgericht erwog, <ref-law> schliesse nicht aus, dass - abgesehen vom dort genannten Fall - in anderen Fällen ebenso wichtige Gründe vorliegen können, um einem Gesuchsteller den Erwerb des väterlichen Namens zu bewilligen.
4.5 Schliesslich wird in der Lehre einhellig die Auffassung vertreten, der Gesetzgeber habe in <ref-law> anerkannt, dass ein wichtiger Grund im Sinne von <ref-law> zur Namensänderung vorliegt, wenn das aussereheliche Kind beim Vater aufwächst und diesem nach <ref-law> die elterliche Sorge übertragen ist (Hegnauer, a.a.O., N. 81 zu <ref-law>, N. 80 zu <ref-law>; Guinand, ZZW 1980 S. 358; Stettler, Schweizerisches Privatrecht, Bd. III/2, S. 460; Bühler, Basler Kommentar, Zivilgesetzbuch I, 2. Aufl. 2002, N. 27 zu <ref-law>; Deschenaux/Steinauer, Personnes physiques et tutelle, 4. Aufl. 2001, S. 134 Rz. 430; Tuor/Schnyder/ Rumo-Jungo, Das Schweizerische Zivilgesetzbuch, 12. Aufl. 2002, S. 399; Meier/Stettler, Droit de la filiation, 3. Aufl. 2006, S. 105 Rz. 192; Bucher, Natürliche Personen und Persönlichkeitsschutz, 3. Aufl. 1999, S. 212 Rz. 815; Häfliger, a.a.O, S. 252 f.).
4.6 Nach dem Dargelegten handelt es sich beim Umstand, dass ein aussereheliches Kind beim Vater als Träger der elterlichen Sorge aufwächst, um einen wichtigen Grund im Sinne von <ref-law>. Im konkreten Fall wächst die (im Zeitpunkt des Erlasses des angefochtenen Beschlusses) 8-jährige Berufungsklägerin als Kind unverheirateter Eltern bei ihrem Vater auf, dem nach <ref-law> die elterliche Sorge seit Jahren übertragen ist. Vor diesem Hintergrund hat das Obergericht rechtserhebliche Umstände verkannt und gegen Bundesrecht verstossen, wenn es das Vorliegen eines wichtigen Grundes zur Namensänderung verneint hat, zumal keine Anhaltspunkte ersichtlich sind, welche die Erheblichkeit dieser Umstände in Frage stellen würden. Die Berufung ist begründet und der Berufungsklägerin ist die Änderung ihres Familiennamens von "X._" in "Y._" zu bewilligen.
4.7 Bei diesem Ergebnis erübrigt sich die Erörterung, ob - wie die Berufungsklägerin unter Hinweis auf <ref-law> meint - eine verfassungskonforme Auslegung von Art. 30 Abs. 1 i.V.m. <ref-law> ebenfalls dazu führe, dass die Änderung des Familiennamens zu bewilligen sei. Ebenso wenig braucht geprüft zu werden, ob das Obergericht zu Recht angenommen hat, dass die weiteren einzelnen Nachteile, welche die Berufungsklägerin mit dem Tragen des Namens ihrer Mutter verbindet, für sich alleine (d.h. ohne Berücksichtigung, dass die Berufungsklägerin als Kind unverheirateter Eltern beim Vater als Träger der elterlichen Sorge aufwächst) keine wichtigen Gründe im Sinne von <ref-law> darstellen, um eine Namensänderung zu bewilligen.
5. Aus diesen Gründen ist die Berufung gutzuheissen und das angefochtene Urteil ist in Ziff. 2-5 aufzuheben. Der Berufungsklägerin ist antragsgemäss die Änderung ihres Familiennamens von "X._" in "Y._" zu bewilligen. Bei diesem Verfahrensausgang wird die Berufungsbeklagte kosten- und entschädigungspflichtig (Art. 156 Abs. 1 und Art. 159 Abs. 1 OG). Die Voraussetzungen, um der Berufungsbeklagten für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege zu gewähren, sind erfüllt (Art. 152 OG). Über die Gerichtskosten und Parteientschädigungen des kantonalen Verfahrens wird das Obergericht zu entscheiden haben (Art. 157 und Art. 159 Abs. 6 OG). Das vorliegende Urteil ist der kantonalen Aufsichtsbehörde über das Zivilstandswesen mitzuteilen (Art. 40 Abs. 1 lit. e, Art. 43 Abs. 1 und 2 ZStV).

Demnach erkennt das Bundesgericht:
1. Die Berufung wird gutgeheissen und die Ziffern 2-5 des Beschlusses des Obergerichts des Kantons Zürich, II. Zivilkammer, vom 12. Dezember 2005 werden aufgehoben.
2. Durch Namensänderung gemäss <ref-law> erhält die Berufungsklägerin A.X._, geboren im Jahre 1997, von S._, Tochter der B.X._ und des C.Y._, den Familiennamen Y._.
3. Das Gesuch der Berufungsbeklagten um unentgeltliche Rechtspflege wird gutgeheissen, und es wird ihr Rechtsanwältin Barbara Umbricht Lukas als Rechtsbeistand beigegeben.
4. Die Gerichtsgebühr von Fr. 2'000.-- wird der Berufungsbeklagten auferlegt, einstweilen aber auf die Bundesgerichtskasse genommen.
5. Die Berufungsbeklagte hat die Berufungsklägerin mit Fr. 1'000.-- zu entschädigen.
6. Dem unentgeltlichen Rechtsbeistand der Berufungsbeklagten, Rechtsanwältin Barbara Umbricht Lukas, wird aus der Bundesgerichtskasse ein Honorar von Fr. 1'000.-- ausgerichtet.
7. Die Sache wird zur Neuverlegung der Kosten und Entschädigung für das kantonale Verfahren an das Obergericht zurückgewiesen.
8. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, sowie der Direktion der Justiz und des Innern des Kantons Zürich (zuhanden der kantonalen Aufsichtsbehörde für das Zivilstandswesen) schriftlich mitgeteilt.
Lausanne, 22. Mai 2006
Im Namen der II. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: