Sachverhalt:
A. A._ und B._ (Beschwerdeführer) belangten die X._ AG (Beschwerdegegnerin) vor dem Bezirksgericht Bülach im Sinne einer Teilklage auf Zahlung von Fr. 31'840.-- aus Werkeigentümerhaftung. Das Bezirksgericht wies die Klage am 9. Juli 2008 ab. Dieses Urteil hob das Obergericht des Kantons Zürich am 9. Juni 2010 auf und wies das Verfahren zur Durchführung eines Beweisverfahrens an das Bezirksgericht zurück.
B. Mit Eingabe vom 21. April 2011 reichten die Beschwerdeführer dem Bezirksgericht ein Ablehnungsbegehren gegen dessen Vizepräsidenten Andreas Fischer ein. Sie brachten dazu vor, der abgelehnte Richter habe das Nichterscheinen eines Zeugen genutzt, um die Parteien zu fragen, ob Vergleichsgespräche geführt worden seien. Als diese verneint hätten, habe der abgelehnte Richter erklärt, er erachte das Prozessrisiko der Beschwerdeführer trotz der obergerichtlichen Rückweisung nach wie vor als sehr gross. Hierauf habe er die Beschwerdeführer gefragt, ob sie sich einen Klagerückzug vorstellen könnten. Deren Antwort sei negativ ausgefallen. Mit dem beschriebenen Verhalten habe der abgelehnte Richter zumindest den Eindruck erweckt, er habe sich eine abschliessende Meinung gebildet, die auch durch die unmittelbar bevorstehende Beweisverhandlung mit Zeugenbefragung nicht mehr geändert werden könne. Der abgelehnte Richter erscheine deshalb als befangen. Ausserdem sei er vorbefasst, da er bereits vor der Rückweisung am Verfahren mitgewirkt habe. Schliesslich sei auch die landgerichtliche Zusammensetzung des Spruchkörpers mit dem abgelehnten Richter als Juristen unter Laienrichtern, dessen Meinung faktisch prozessentscheidende Bedeutung zukomme, geeignet, ihn als befangen erscheinen zu lassen.
C. Am 4. Mai 2011 überwies der abgelehnte Richter das Ablehnungsbegehren zuständigkeitshalber an die Verwaltungskommission des Obergerichts des Kantons Zürich. Gleichzeitig gab er die gewissenhafte Erklärung ab, er fühle sich unbefangen, und er erläuterte die Ereignisse vom 8. April 2011 sowie seine damals abgegebene Meinungsäusserung aus seiner Sicht. Mit Beschluss vom 4. Juli 2011 wies die Verwaltungskommission das Ablehnungsbegehren ab. Auf die hiegegen erhobene Beschwerde in Zivilsachen trat das Bundesgericht am 21. September 2011 nicht ein, weil die Verwaltungskommission nicht auf Rechtsmittel hin, sondern als erste und einzige Instanz entschieden hatte, womit der Anforderung gemäss <ref-law> nicht genüge getan war (Urteil des Bundesgerichts 4A_534/2011 vom 21. September 2011 mit Hinweis auf <ref-ruling> E. 2.2). Hierauf gelangten die Beschwerdeführer nach wiederhergestellter Frist an die Rekurskommission des Obergerichts des Kantons Zürich mit den Anträgen, den Beschluss der Verwaltungskommission vom 4. Juli 2011 aufzuheben und das Ausstandsgesuch gutzuheissen. Die Rekurskommission wies die Beschwerde am 7. Juni 2012 ab.
D. Die Beschwerdeführer beantragen dem Bundesgericht mit Beschwerde in Zivilsachen, den Beschluss des Obergerichts vom 7. Juni 2012 aufzuheben und ihr Ausstandsgesuch gutzuheissen. Ihrem Gesuch um Gewährung der aufschiebenden Wirkung gab das Bundesgericht am 6. August 2012 statt. Sowohl die Beschwerdegegnerin als auch die Rekurskommission des Obergerichts haben auf Vernehmlassung verzichtet.

Erwägungen:
1. Gemäss <ref-law> ist die Beschwerde zulässig gegen Entscheide letzter kantonaler Instanzen. Bei der letzten kantonalen Instanz muss es sich um ein oberes Gericht handeln (<ref-law>). Zudem muss dieses obere Gericht als Rechtsmittelinstanz entscheiden (<ref-law>), es sei denn, es liege einer der - hier nicht gegebenen - Ausnahmefälle von Art. 75 Abs. 2 lit. a bis c BGG vor. Die den Kantonen zur Anpassung ihrer Bestimmungen an <ref-law> gewährte Übergangsfrist (<ref-law>) ist mit Inkrafttreten der schweizerischen Zivilprozessordnung am 1. Januar 2011 abgelaufen. Seit dem 1. Januar 2011 ist somit die Beschwerde in Zivilsachen, wie im Übrigen auch die subsidiäre Verfassungsbeschwerde (<ref-law>), nur noch zulässig gegen Urteile letzter kantonaler Instanzen, die zugleich obere Gerichte sind und - unter Vorbehalt der Ausnahmen - auf Rechtsmittel hin entschieden haben (<ref-ruling> E. 2.1 S. 426 mit Hinweis).
1.1 Die Beschwerdeführer halten dafür, der vorinstanzliche Entscheid erfülle die Anforderungen von <ref-law> nicht und verletzte daher Bundesrecht. Der Grundsatz der "double instance" erfordere eine Hierarchie, die Prüfung eines Entscheids einer untergeordneten durch eine übergeordnete gerichtliche Instanz, einen gerichtlichen Instanzenzug. Über ihr Ausstandsgesuch habe aber zweimal das Obergericht entschieden, einmal als Verwaltungskommission und einmal als Rekurskommission.
1.2 Art. 75 Abs. 2 Satz 1 und 2 BGG stellen keine bestimmten Anforderungen an die Eigenschaften der ersten Instanz. Diese muss zum Beispiel nicht ihrerseits als Rechtsmittelinstanz entschieden haben. Es muss sich dabei nicht einmal um eine richterliche Behörde handeln. Das BGG verlangt einzig, dass erstinstanzlich ergangene Entscheide bei einem oberen kantonalen Gericht angefochten werden können (<ref-ruling> E. 2.4.1.5 S. 224 f. mit Hinweisen). Daraus ist abzuleiten, dass als erste Instanz auch ein kantonales Obergericht in Frage kommt. Die Zulässigkeit der Beschwerde hängt einzig davon ab, ob ein erstinstanzlicher Entscheid einer nicht näher definierten Instanz - unter Vorbehalt der erwähnten Ausnahmen - an einen Spruchkörper des oberen kantonalen Gerichts als letzte Instanz weitergezogen werden kann (<ref-ruling> E. 2.1 S. 426 mit Hinweis). Dieser Anforderung wird die Vorinstanz gerecht: Die Rekurskommission, die den angefochtenen Entscheid gefällt hat, wird aus den fünf amtsältesten Mitgliedern des Obergerichts, die nicht als Mitglieder oder Ersatzmitglieder der Verwaltungskommission angehören, gebildet (§ 19 Abs. 4 der Verordnung über die Organisation des Obergerichts vom 3. November 2010; LS 212.51). Der angefochtene Entscheid der Rekurskommission des Obergerichts erging auf Beschwerde gegen den das Ablehnungsbegehren erstinstanzlich abweisenden Ablehnungsentscheid der Verwaltungskommission, mithin als Rechtsmittelentscheid eines Spruchkörpers. Dass Vor- und Überprüfungsinstanz aus Mitgliedern desselben Gerichts zusammengesetzt sind, schadet daher nicht (vgl. Urteil des Bundesgerichts 5A_784/2011 vom 23. März 2012, in welchem dieses mit Blick auf das Anfechtungsobjekt die Eintretensvoraussetzungen, mithin auch jene der double instance, für ein Urteil des Obergerichts des Kantons Zürich als gegeben betrachtete, mit dem eine Beschwerde gegen die Gewährung der unentgeltlichen Rechtspflege durch den Vizepräsidenten desselben Obergerichts abgewiesen worden war). Ein Verstoss gegen <ref-law> ist nicht auszumachen.
2. Die Beschwerdeführer haben vor Vorinstanz die Zuständigkeit der Rekurskommission des Obergerichts zur Beurteilung von Beschwerden gegen erstinstanzliche Ausstandsentscheide der Verwaltungskommission des Obergerichts bestritten.
2.1 Dazu erwog die Vorinstanz, nach <ref-law> seien erstinstanzliche Entscheide über Ablehnungsbegehren mit Beschwerde anfechtbar. Beschwerdeinstanz sei nach § 48 des Gesetzes über die Gerichts- und Behördenorganisation im Zivil- und Strafprozess vom 10. Mai 2010 (GOG; LS 211.1) das Obergericht. Diese Bestimmung, auf welche die Zuständigkeit der Rekurskommission in erster Linie gestützt werde, stelle eine genügende gesetzliche Grundlage dar. Einzig, wer innerhalb des Obergerichts konkret für die Beurteilung derartiger Beschwerden zuständig sei, werde durch die Verordnung über die Organisation des Obergerichts geregelt.
2.2 Die Beschwerdeführer halten vor Bundesgericht daran fest, die Vorinstanz verletze mit der Annahme einer hinreichenden gesetzlichen Grundlage, auf der die Schaffung der Rekurskommission beruhe, Art. 6 Abs. 1 EMRK, <ref-law> und Art. 73 der Verfassung des Kantons Zürich vom 27. Februar 2005 (LS 101), wonach jede Person Anspruch auf ein unabhängiges, durch Gesetz geschaffenes Gericht habe. Dabei müsse es sich um ein Gesetz im formellen Sinn handeln. Die obergerichtliche Verordnung sei keine formalgesetzliche Grundlage zur Schaffung einer gerichtlichen Rechtsmittelinstanz, zumal sie - anders als nach dem altrechtlichen § 49 Abs. 1 des Gerichtsverfassungsgesetzes vom 13. Juni 1976 (GVG; Aufhebungsdatum: 1. Januar 2011) - gemäss § 42 GOG keiner Genehmigung durch den Kantonsrat mehr bedürfe.
2.3 Wird die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung) geltend gemacht, kommt der Grundsatz der Rechtsanwendung von Amtes wegen (<ref-law>) nicht zum Tragen, sondern es gilt das Rügeprinzip (<ref-law>). Es ist im Einzelnen darzulegen, inwiefern verfassungsmässige Rechte missachtet wurden oder der Entscheid offensichtlich unhaltbar ist. Der Richter untersucht den angefochtenen Entscheid nicht von sich aus umfassend auf seine Verfassungsmässigkeit, sondern beschränkt sich auf die Prüfung der in der Beschwerde rechtsgenüglich vorgebrachten Rügen (<ref-law>; <ref-ruling> E. 6 S. 397; <ref-ruling> E. 1.4.3 S. 255). Die Beschwerdeschrift muss eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Erlass oder Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen; auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. 2.2 S. 246 mit Hinweisen).
2.4 Das kantonale Recht regelt die sachliche und funktionelle Zuständigkeit der Gerichte, soweit das Gesetz nichts anderes bestimmt (<ref-law>). Was die Zuständigkeit des Obergerichts als solchen zur Beurteilung von Beschwerden gegen Ausstandsentscheide anbelangt, stellen die Beschwerdeführer nicht in Abrede, dass sich diese aus <ref-law> i.V.m. mit § 48 GOG, mithin aus einer hinreichenden gesetzlichen Grundlage ableitet. Sie bestreiten einzig die Zuständigkeit des spezifischen Spruchkörpers der Rekurskommission, da diese lediglich auf einer Verordnung und nicht auf einem Gesetz im formellen Sinne beruhe.
2.4.1 <ref-law> garantiert den Anspruch auf ein durch Gesetz geschaffenes, zuständiges, unabhängiges und unparteiisches Gericht. Zur Verhinderung von Missbrauch und Manipulation bzw. zum Ausschluss jeglichen entsprechenden Anscheins oder Verdachts sollen Gerichte und ihre Zuständigkeiten (in persönlicher, zeitlicher, örtlicher und sachlicher Hinsicht) durch generell-abstraktes Verfahrensrecht im Voraus bestimmt sein. Nach dem Wortlaut der Verfassungsbestimmung muss sich die Gerichtsorganisation auf ein formelles Gesetz stützen. Untergeordnete Fragen können aber der Exekutive oder der Justizbehörde zur Regelung delegiert werden (<ref-ruling> E. 3.3 S. 133 mit Hinweisen; Urteil des Bundesgerichts 2C_381/2010 vom 17. November 2011 E. 2.2, publ. in: ZBl 113/2012 S. 268 f.).
2.4.2 Von dieser Möglichkeit hat der kantonale Gesetzgeber in § 42 Abs. 1 GOG, der die Plenarversammlung anweist, eine Verordnung über die Organisation des Obergerichts zu erlassen, Gebrauch gemacht und die Kompetenz zum Erlass der Verordnung, gestützt auf welche die Rekurskommission eingesetzt wurde, an das Obergericht delegiert. Inwiefern eine derartige Delegation unzulässig sein sollte (<ref-ruling> E. 3.3 S. 133 mit Hinweisen; zit. Urteil 2C_381/2010 E. 2.2), ist der Beschwerde nicht zu entnehmen. Insoweit genügt diese den Begründungsanforderungen (<ref-law>) nicht. Dass es sich bei der Verordnung nicht um ein Gesetz im formellen Sinne handelt, schadet daher nicht.
2.5 Im Übrigen behaupten die Beschwerdeführer sinngemäss, es fehle der Vorinstanz an der notwendigen Unabhängigkeit wegen der institutionellen Zugehörigkeit zu demselben Obergericht, dem auch die Verwaltungskommission angehört. Weshalb aus diesem Grunde Zweifel an der unabhängigen Überprüfung, gegebenenfalls Verbesserung der erstinstanzlichen Entscheidung angebracht sein sollen, zeigen die Beschwerdeführer jedoch nicht auf. Im Übrigen handelt es sich bei der erstinstanzlichen Zuständigkeit der Verwaltungskommission zur Beurteilung von Ausstandsbegehren gegen Mitglieder der Bezirksgerichte (§ 101 Abs. 1 GVG in Verbindung mit § 106 Abs. 1 GVG entsprechend dem neurechtlichen § 127 lit. d GOG) möglicherweise ohnehin nur um eine übergangsrechtliche Regelung, da das Obergericht mit Kreisschreiben vom 6. Oktober 2010 Ziff. 9 lit. c diesbezüglich abweichend von § 127 lit. d GOG die Zuständigkeit der Bezirksgerichte vorsieht mit der Begründung, die kantonale Regelung widerspreche in diesem Punkte <ref-law> (HAUSER/SCHWERI/LIEBER, GOG, 2012, N. 2 zu § 127 GOG; vgl. auch DIGGELMANN, in: Schweizerische Zivilprozessordnung [ZPO]: Kommentar, Brunner und andere [Hrsg.], 2011, N. 8 zu <ref-law>, Fussnote 15). Vorliegend bestimmt sich die Zuständigkeit der Verwaltungskommission noch nach dem gemäss <ref-law> anwendbaren alten Prozessrecht, weshalb zumindest übergangsrechtlich die Zuständigkeit der Rekurskommission mit Blick auf deren Unabhängigkeit unbedenklich erscheint.
2.6 Insgesamt erweist sich die Rüge fehlender formalgesetzlicher Zuständigkeit der Vorinstanz als obere kantonale Rechtsmittelinstanz als unbegründet.
3. In der Sache selbst führte die Vorinstanz mit Blick auf die Frage der Befangenheit des erstinstanzlichen Richters aus, die Einschätzung der Prozesschancen sei im Zusammenhang mit der Diskussion über eine allfällige Vergleichsbereitschaft (beziehungsweise einen möglichen Verfahrensabschluss) in sachlicher Weise aufgrund der Gegebenheiten im Prozess vor dem Bezirksgericht erfolgt und erscheine angemessen, zumal die Beweislast bei den Beschwerdeführern liege und die vorgeladenen Zeugen zu ca. 20 Jahre zurückliegenden Geschehnissen auszusagen hatten. Anzeichen dafür, dass der Abgelehnte durch seine Äusserungen zu verstehen gegeben habe, das Ergebnis der Zeugenbefragung spiele für den Prozessausgang keine Rolle mehr, lägen nicht vor. Vielmehr habe der Abgelehnte "seine Äusserung gestützt auf die bisherigen Erkenntnisse und Beweismittel vor der Abnahme der weiteren, allenfalls massgebenden Beweismittel und im Wissen darum, dass noch nicht alle Beweismittel erhoben wurden, gemacht". Von einem Richter sei zu erwarten, dass er die Streitsache auch nach Aufhebung des Entscheids objektiv und unparteiisch behandle (<ref-ruling> E. 2b). Die blosse Kundgabe der Auffassung über die Prozessaussichten im Zusammenhang mit der Diskussion über eine allfällige Vergleichsbereitschaft lasse den Abgelehnten bei objektiver Betrachtung nicht als befangen erscheinen. Seine Aussage sei mit der gebotenen grossen Zurückhaltung erfolgt.
3.1 Die Beschwerdeführer erblicken darin eine Verletzung der sich aus <ref-law> und Art. 6 Ziff. 1 EMRK ergebenden Grundsätze. Sie sind der Ansicht, der Abgelehnte habe es bei seiner Prozesseinschätzung an der Zurückhaltung, und erst recht an der gemäss Rechtsprechung geforderten grossen Zurückhaltung fehlen lassen. Seine äusserst kurze und ohne weitere Ausführungen oder Vorbehalte in den Raum gestellte Meinungsäusserung sei an sich schon geeignet gewesen, den Anschein der Befangenheit zu erwecken, was vor dem Hintergrund der obergerichtlichen Rückweisung zur Durchführung des Beweisverfahrens umso mehr gelte. Er habe den Eindruck erweckt, sich ein abschliessendes Urteil gebildet zu haben, indem er trotz der obergerichtlichen Rückweisung und bevorstehenden Zeugenbefragung "weiterhin" von schlechten Gewinnaussichten sprach.
3.2 Mit diesen Vorbringen gehen die Beschwerdeführer nicht rechtsgenügend auf die Ausführungen der Vorinstanz ein. Sie lassen zudem mit ihrem Hinweis auf das Bundesgerichtsurteil 1B_407/2010 vom 4. Mai 2011 (<ref-ruling>) ausser Acht, dass dem dort zu beurteilenden Fall eine in wesentlichen Punkten von der vorliegenden abweichende Konstellation zugrunde lag.
3.2.1 In dem von den Beschwerdeführern angeführten Urteil hielt das Bundesgericht ein Vorgehen des Kammervorsitzenden für bedenklich, mit welchem dieser nach Einreichung der Berufung und Stellung von Beweisanträgen durch einen Angeklagten dessen Verteidiger in einem Brief nach Beurteilung der Sach- und Rechtslage ersucht hatte, mit seinem Klienten ernsthaft einen Rückzug der Berufung wegen schlechter Erfolgsaussichten zu diskutieren und dem Verteidiger unmittelbar nach Eingang der negativen Antwort mitteilte, er werde am weiteren Verfahren nicht mitwirken. Daraus leitete das Bundesgericht sinngemäss ab, dem Oberrichter seien die in <ref-ruling> dargelegten Grundsätze bekannt gewesen, wonach die aktive Mitteilung der vorläufigen Einschätzung seitens des Referenten schon im Voraus den Eindruck erwecke, der Referent habe sich bereits eine abschliessende Meinung gebildet, das Verfahren sei auch unter Beachtung der noch bevorstehenden Berufungsverhandlung nicht mehr offen, der Prozess bereits verloren; es gehe dem Referenten einzig um eine möglichst rasche Erledigung der Streitsache. Die Erklärung des Ausstands als Folge des bewussten Herbeiführens eines derartigen Ausstandsgrundes durch die Justizperson stehe im Widerspruch zur Pflicht, die eigene Unabhängigkeit und die anhaltende Offenheit des Verfahrens sicherzustellen.
3.2.2 Im Gegensatz dazu teilte der Abgelehnte im vorliegenden Falle den anwaltlich vertretenen Parteien seine Meinung im Zusammenhang mit der Diskussion über eine allfällige Vergleichsbereitschaft in einem Zivilprozess mit. Nach der Rechtsprechung steht nicht jegliche Mitteilung einer vorläufigen Einschätzung des Referenten mit den Garantien von <ref-law> und Art. 6 Ziff. 1 EMRK im Widerspruch, umso weniger, wenn die Parteien anwaltlich vertreten sind und die richterliche Einschätzung daher fachgerecht eingeordnet werden kann. In einer zivilrechtlichen Angelegenheit kann der Referent im Einverständnis mit den Parteien Vergleichsverhandlungen einleiten und seine provisorische Einschätzung mit Zurückhaltung und unter dem Vorbehalt der förmlichen Streitentscheidung zum Ausdruck bringen (<ref-ruling> E. 2.4 S. 244; <ref-ruling> E. 3.6 S. 119 f.). Der abgelehnte Richter eröffnete den Parteien, nachdem er sie nach Vergleichsgesprächen gefragt hatte, dass er selbst das Prozessrisiko weiterhin als erheblich einstufe. Diese Einschätzung ist im Hinblick darauf, dass die Zeugen zu Geschehnissen auszusagen hatten, die 20 Jahre zurücklagen, und ein Zeuge nicht erschienen war, sachlich vertretbar und vermag objektiv betrachtet keinen Anschein der Befangenheit zu erwecken. Dass die Beschwerdeführer nicht erkannt hätten, aus welchen Gründen der abgelehnte Richter zu seiner Beurteilung kam, behaupten sie nicht. Gründe zur Annahme, der abgelehnte Richter würde seine vorläufige Meinung auch dann nicht ändern, wenn die Zeugenaussagen überzeugend zugunsten der Beschwerdeführer lauten würden, bezeichnen die Beschwerdeführer nicht. Solche sind bei objektiver Betrachtung auch nicht ersichtlich. Damit erweist sich der Vorwurf der Verletzung von <ref-law> als unbegründet.
4. Aus den dargelegten Gründen ist die Beschwerde abzuweisen. Bei diesem Verfahrensausgang werden die Beschwerdeführer für das bundesgerichtliche Verfahren unter solidarischer Haftung kostenpflichtig. Da sich die Beschwerdegegnerin nicht hat vernehmen lassen, haben sie keine Parteientschädigung zu entrichten.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, Rekurskommission, schriftlich mitgeteilt.
Lausanne, 19. September 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Luczak