Sachverhalt:
A. Y._ ist als Ersatzrichterin am Bezirksgericht Winterthur mit dem Scheidungsverfahren der Eheleute X._ befasst. AX._ verlangte mit Eingabe vom 19. August 2005 den Ausstand der Ersatzrichterin Y._. Diese überwies die Eingabe zusammen mit der gewissenhaften Erklärung im Sinne von § 100 des Gerichtsverfassungsgesetzes vom 13. Juni 1976 (GVG), dass sie sich nicht befangen fühle, der Verwaltungskommission des Zürcher Obergerichts zur Entscheidung.
Die Verwaltungskommission wies das Ablehnungsbegehren am 21. September 2005 ab.
B. Mit staatsrechtlicher Beschwerde vom 22. Oktober 2005 beantragt AX._, sein Ablehnungsgesuch gutzuheissen und Y._ in den Ausstand zu versetzen. Für den Fall, dass dies nicht möglich sei, beantragt er, sein Scheidungsverfahren einem anderen Kanton zuzuweisen.
Das Obergericht verzichtet auf Vernehmlassung. Y._ weist die von AX._ gegen sie erhobenen Vorwürfe zurück und bekräftigt, sich nicht befangen zu fühlen; einer Umteilung des Verfahrens an einen anderen Richter oder ein anderes Gericht widersetze sie sich hingegen nicht, wenn dies als im Hinblick auf die materielle Lösung der im Scheidungsverfahren anstehenden Probleme sinnvoll erscheine. BX._ beantragt, die Beschwerde abzuweisen.
Mit unverlangter Eingabe vom 3. Dezember 2005 liefert AX._ "erste Elemente einer Antwort" auf die Vernehmlassungen und verwahrt sich insbesondere gegen den Vorwurf, das Scheidungsverfahren zu hintertreiben. Im Übrigen würden es ihm seine Deutschkenntnisse nicht erlauben, ohne eine genaue Übersetzung der Vernehmlassungen sachgerecht zu replizieren. Er werde bis zum 15. Januar 2006 die Argumente Y._s und seiner Frau Punkt für Punkt widerlegen.
Mit Eingabe vom 9. Januar 2006 vervollständigt AX._ seine Replik.

Das Bundesgericht zieht in Erwägung:
1. Der angefochtene Entscheid der Verwaltungskommission über die Abweisung des Ablehnungsbegehrens schliesst das Scheidungsverfahren nicht ab, sondern lässt im Gegenteil dessen Fortführung zu. Es handelt sich um einen Zwischenentscheid im Sinne von Art. 87 Abs. 1 OG, gegen den die staatsrechtliche Beschwerde zulässig ist. Der Beschwerdeführer ist nach Art. 88 OG befugt, sich gegen die Abweisung seiner Befangenheitsrüge zur Wehr zu setzen, wobei er allerdings einzig die Aufhebung des angefochtenen Entscheids verlangen kann. Sein Antrag, das Scheidungsverfahren einem anderen Kanton zuzuweisen, scheitert an der kassatorischen Natur der staatsrechtlichen Beschwerde.
Die übrigen Sachurteilsvoraussetzungen sind erfüllt, sodass auf die Beschwerde, unter dem Vorbehalt gehörig begründeter Rügen (Art. 90 Abs. 1 lit. b OG; <ref-ruling> E. 3c; <ref-ruling> E. 1b; <ref-ruling> E. 1c), einzutreten ist.
2. Der Beschwerdeführer macht sinngemäss geltend, die Verwaltungskommission habe die Garantie des unparteiischen, unvoreingenommenen und unbefangenen Richters verletzt, wie sie sich aus <ref-law> und Art. 6 Ziff. 1 EMRK ergibt.
Nach der in <ref-law> und in Art. 6 Ziff. 1 EMRK enthaltenen Garantie des verfassungsmässigen Richters hat der Einzelne Anspruch darauf, dass seine Sache von einem unparteiischen, unvoreingenommenen und unbefangenen Richter ohne Einwirken sachfremder Umstände entschieden wird. Liegen bei objektiver Betrachtungsweise Gegebenheiten vor, die den Anschein der Befangenheit und die Gefahr der Voreingenommenheit zu begründen vermögen, so ist die Garantie verletzt (<ref-ruling> E. 3a mit Hinweisen). Verfahrens- oder andere Rechtsfehler, die einem Richter unterlaufen, können nach der Rechtsprechung den Anschein der Befangenheit allerdings nur begründen, wenn sie wiederholt begangen wurden oder so schwer wiegen, dass sie Amtspflichtverletzungen darstellen (<ref-ruling> E. 5; 135 E. 3a).
3. In diesem Verfahren ist einzig zu prüfen, ob die Verwaltungskommission im angefochtenen Entscheid das Ablehnungsbegehren des Beschwerdeführers ohne Verfassungsverletzung abweisen konnte.
3.1 Die Verwaltungskommission ist im angefochtenen Entscheid zu Recht davon ausgegangen, dass die Ersatzrichterin Y._ nicht schon deswegen befangen ist, weil sie im Eheschutzverfahren in den Jahren 2002 - 2003 Entscheidungen traf, die nicht den Vorstellungen des Beschwerdeführers entsprachen. Sie hat ebenfalls zutreffend festgestellt, dass nur besonders schwere und/oder wiederholte Verfahrensfehler die Befangenheit eines Richters begründen können. In concreto hat die Verwaltungskommission erwogen, solche seien nicht ersichtlich, was schon daraus hervorgehe, dass der vom Beschwerdeführer angefochtene Entscheid der Ersatzrichterin vom Obergericht geschützt und erst vom Kassationsgericht unter Hinweis auf seine neuere Rechtsprechung wegen ungenügender Tatsachenermittlung aufgehoben worden sei. Stehe damit aber fest, dass der Ersatzrichterin Y._ keine groben Verfahrensfehler vorzuwerfen seien, brauche auf die vom Beschwerdeführer vorgebrachten 17 Gründe, welche alle das von dieser in den Jahren 2002/2003 geleitete Verfahren beträfen, nicht näher eingegangen zu werden.
3.2 Es trifft zu, dass nur schwere oder wiederholte Verfahrensfehler die Befangenheit eines Richters begründen können. Das Obergericht hat das Vorgehen der Ersatzrichterin Y._ geprüft und geschützt, und auch das Kassationsgericht hat ihr nach der unbestrittenen Darstellung der Verwaltungskommission im angefochtenen Entscheid keine schweren Verfahrensfehler vorgeworfen. Die Verwaltungskommission konnte unter diesen Umständen ohne weiteres davon ausgehen, dass sie keine solchen begangen hat und brauchte sich daher mit den vom Beschwerdeführer erhobenen 17 Vorwürfen nicht weiter auseinanderzusetzen. Die Befangenheitsrüge ist offensichtlich unbegründet.
3.3 Ablehnungsgründe sind zudem nach Treu und Glauben ohne Verzug geltend zu machen (<ref-ruling> E. 2; <ref-ruling> E. 5a; <ref-ruling> E. 3a). Es erscheint daher ohnehin mehr als fraglich, ob der Beschwerdeführer überhaupt befugt war, sein am 19. August 2005 eingereichtes Ablehnungsbegehren mit Verfahrensfehlern zu begründen, die die Ersatzrichterin Y._ angeblich in den Jahren 2002 und 2003 begangen haben soll. Die Verwaltungskommission hätte diese Ablehnungsgründe jedenfalls auch ohne Verfassungsverletzung als verspätet zurückweisen können. Im Ergebnis ist der angefochtene Entscheid daher auch aus diesem Grund nicht zu beanstanden.
4. Die Beschwerde ist somit abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Kosten (Art. 156 OG), und er hat der privaten Beschwerdegegnerin eine angemessene Parteientschädigung zu bezahlen (Art. 159 OG).

Demnach erkennt das Bundesgericht
im Verfahren nach Art. 36a OG:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat der privaten Beschwerdegegnerin eine Parteientschädigung von Fr. 1'500.-- zu bezahlen.
4. Dieses Urteil wird den Parteien, Y._ und der Verwaltungskommission des Obergerichts des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 27. Januar 2006
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident:
Der Gerichtsschreiber: