Sachverhalt:
A. Das Ehepaar B._ und A._ (Beschwerdeführer) führte Mitte der Neunzigerjahre einen grösseren Umbau und Neubau ihrer Villa in D._ aus. Am 14. November 1995 schlossen sie, vertreten durch die Y._ AG, mit der Firma X._ + Co AG (Beschwerdegegnerin) einen ersten Werkvertrag über die Lieferung und den Einbau von Heizungs-, Lüftungs- und Klimaanlagen in ihrer Villa. Am 29. August 1996 schlossen sie einen zweiten Werkvertrag über die Lieferung und den Einbau einer Kälteanlage im gleichen Bauobjekt.
B. Mit Klage vom 2. Juli 2001 an das Bezirksgericht Meilen verlangte die Beschwerdegegnerin die Bezahlung ausstehender Rechnungsbeträge in Gesamthöhe von Fr. 82'413.85. Die Beschwerdeführer anerkannten diese Forderung grundsätzlich im Umfang von Fr. 74'210.55, machten aber ihrerseits Verrechnungsforderungen in einer den eingeklagten Betrag übersteigenden Höhe geltend. Mit der Kälteanlage hatte es verschiedene Probleme gegeben, welche nach Darstellung der Beschwerdeführer zu Kosten und diversen Schadenspositionen geführt hatten. Die Beschwerdegegnerin machte geltend, dass nicht sie, sondern der von den Beschwerdeführern beauftragte Ingenieur, C._, für die Probleme verantwortlich sei. Zudem bestritt sie einzelne Schadenspositionen. Mit Urteil vom 20. Dezember 2007 verpflichtete das Bezirksgericht Meilen die Beschwerdeführer je zur Hälfte, der Beschwerdegegnerin Fr. 78'823.95 nebst Zins zu 5% seit 21. September 1999 zu bezahlen. Im Mehrbetrag wies es die Klage ab.
Dagegen erhoben die Beschwerdeführer beim Obergericht des Kantons Zürich Berufung und beantragten, der Fall sei zur Ergänzung des Beweisverfahrens und zur Neubeurteilung an das Bezirksgericht zurückzuweisen. Präzisierend beantragten sie die Abweisung der Klage. Die Beschwerdegegnerin schloss auf Abweisung der Berufung und Bestätigung des Urteils des Bezirksgerichts. Mit Beschluss vom 7. Juli 2009 merkte das Obergericht vor, dass das Urteil des Bezirksgerichts vom 20. Dezember 2007 insoweit in Rechtskraft erwachsen ist, als mit ihm die Klage abgewiesen wurde. Mit Urteil vom 7. Juli 2009 verpflichtete es die Beschwerdeführer je zur Hälfte, der Beschwerdegegnerin Fr. 78'823.95 nebst Zins zu 5% seit 21. September 1999 zu bezahlen.
C. Die Beschwerdeführer beantragen dem Bundesgericht mit Beschwerde in Zivilsachen, das Urteil des Obergerichts vom 7. Juli 2009 sei aufzuheben und die Sache zur Feststellung des Sachverhalts und Neubeurteilung im Sinne der Erwägungen an das Obergericht zurückzuweisen. Eventualiter sei die Klage vollumfänglich abzuweisen. Die Beschwerdegegnerin sei zu verurteilen, Beträge, die ihr von den Beschwerdeführern auf der Basis des angefochtenen Urteils vor dem Entscheid des Bundesgerichts über die vorliegende Beschwerde allenfalls ausbezahlt werden, umgehend zurückzuzahlen.
Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei, und das angefochtene Urteil zu bestätigen. Die Beschwerdeführer seien je zur Hälfte zu verpflichten, der Beschwerdegegnerin insgesamt Fr. 78'823.95 nebst Zins zu 5% seit 21. September 1999 zu bezahlen.
Die Vorinstanz verzichtete auf eine Vernehmlassung.

Erwägungen:
1. Das Rechtsbegehren, wonach die Beschwerdegegnerin zu verurteilen sei, Beträge, die ihr von den Beschwerdeführern auf der Basis des angefochtenen Urteils vor dem Entscheid des Bundesgerichts über die vorliegende Beschwerde allenfalls ausbezahlt werden, umgehend zurückzuzahlen, ist neu und damit unzulässig (<ref-law>), weshalb darauf nicht eingetreten werden kann.
2. Damit ein kantonaler Entscheid mit Beschwerde in Zivilsachen angefochten werden kann, muss der Instanzenzug im Kanton erschöpft sein (<ref-law>). Für Rügen, die mit der Beschwerde in Zivilsachen erhoben werden können, darf kein kantonales Rechtsmittel mehr offen stehen (<ref-ruling> E. 1.3 S. 527). Auf Rügen, die mit kantonaler Nichtigkeitsbeschwerde einer weiteren kantonalen Instanz hätten vorgetragen werden können, ist mangels Letztinstanzlichkeit nicht einzutreten.
Gegen das angefochtene Urteil des Obergerichts war die kantonale Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich nach § 281 des Gesetzes über die Zivilprozessordnung vom 13. Juni 1976 [Zivilprozessordnung, ZPO/ZH; LS 271] zulässig, weshalb es insoweit nicht kantonal letztinstanzlich ist, als es vom Kassationsgericht hätte überprüft werden können. Nach <ref-law>/ZH kann mit Nichtigkeitsbeschwerde geltend gemacht werden, der angefochtene Entscheid beruhe zum Nachteil des Nichtigkeitsklägers auf einer Verletzung eines wesentlichen Verfahrensgrundsatzes (Ziff. 1), auf einer aktenwidrigen oder willkürlichen tatsächlichen Annahme (Ziff. 2) oder auf einer Verletzung klaren materiellen Rechts (Ziff. 3). Ausgeschlossen ist die Nichtigkeitsbeschwerde, wenn das Bundesgericht einen Mangel frei überprüfen kann, wobei sie gemäss <ref-law>/ZH stets zulässig ist, wenn eine Verletzung von Art. 8, 9, 29 oder 30 BV oder von Art. 6 EMRK geltend gemacht wird.
Die Beschwerdeführer haben keine kantonale Nichtigkeitsbeschwerde an das Kassationsgericht erhoben. Sie können das Urteil des Obergerichts somit nur insoweit anfechten, als im Rahmen der Beschwerde in Zivilsachen zulässige Rügen dem Kassationsgericht nicht unterbreitet werden konnten. Ausgeschlossen sind sie insbesondere mit Rügen willkürlicher tatsächlicher Feststellungen. Auf solche Rügen kann mangels Letztinstanzlichkeit nicht eingetreten werden.
3. Die Forderung der Beschwerdegegnerin ist im zugesprochenen Betrag vor Bundesgericht nicht bestritten. Hingegen wehren sich die Beschwerdeführer gegen die Nichtzulassung ihrer verrechnungsweise geltend gemachten Forderungen wegen Mängeln. Zum einen geht es um die Verrechnungsforderung aufgrund der mangelhaften Weinkellerkühlung (vgl. dazu die nachfolgende Erwägung 4), zum anderen um diejenige aufgrund der mangelhaften Isolation der Lüftungskanäle in der Weinkellerdecke (vgl. dazu Erwägung 5 hinten).
4. Die Probleme mit der Weinkellerkühlung führte die Vorinstanz auf Planungsfehler zurück. Sie schloss in eingehender Beweiswürdigung, dass für diese Planungsfehler die Beschwerdegegnerin nicht verantwortlich gemacht werden könne, da die Planung nicht Teil der von ihr geschuldeten Werkleistung gewesen sei. Die Verantwortung für die Planung der Weinkellerkühlung habe dem Ingenieurbüro C._ oblegen. Die Beschwerdeführer seien durch die Y._ AG als Bauleitung vertreten und zudem durch das Ingenieurbüro C._ sachverständig beraten gewesen.
Die Beschwerdeführer rügen eine Verletzung von Art. 174 Abs. 3 SIA-Norm 118, des allgemeinen Grundsatzes, wonach kein Anspruch auf Überwachung besteht, von <ref-law>, von Art. 167 SIA-Norm 118, der Grundregel, wonach eine Haftung des Ingenieurs ohne Einfluss auf die Haftung des Unternehmers bleibe, und von <ref-law>.
Alle diese Rügen bauen jedoch auf einem Sachverhalt auf, der von demjenigen abweicht, den die Vorinstanz - für das Bundesgericht verbindlich (<ref-law>) - festgestellt hat. Die Vorinstanz stellte fest, dass es um Planungsfehler gehe. Die Planung habe aber nicht Bestandteil des Werkvertrags zwischen den Parteien gebildet. Indem die Beschwerdeführer darzulegen versuchen, dass die Beschwerdegegnerin an der Planung mitbeteiligt und hierfür mitverantwortlich gewesen sei, kritisieren sie - richtig besehen - die Beweiswürdigung der Vorinstanz und den von ihr festgestellten Sachverhalt. Mit solcher Kritik sind sie indessen - mangels Letztinstanzlichkeit - ausgeschlossen (vgl. Erwägung 2), wobei ohnehin keine Willkür aufgezeigt wäre. Nach den verbindlichen Feststellungen der Vorinstanz lag in Bezug auf den zwischen den Parteien abgeschlossenen Werkvertrag, der die Planung nicht umfasste, keine Abweichung von der geschuldeten Leistung und somit kein Mangel vor. Die von den Beschwerdeführern angerufenen Bestimmungen und Grundsätze zu den Mängelrechten kommen daher nicht zum Tragen und können nicht verletzt sein. Im Einzelnen ist kurz was folgt anzufügen:
4.1 Art. 174 Abs. 3 SIA-Norm 118 (Ausgabe 1977) steht unter dem Abschnitt "Garantiefrist" und auferlegt dem Unternehmer die Beweislast, wenn streitig wird, ob ein behaupteter Mangel wirklich eine Vertragsabweichung darstellt und daher ein Mangel im Sinne dieser Norm ist. Diese Beweislastregel durchbricht (partiell) den Grundsatz, wonach die Beweislast für das Vorliegen eines Mangels beim Bauherrn liegt. Sie bezieht sich auf jeden Mangel, der während der Garantiefrist gerügt wird (GAUCH, Kommentar zur SIA-Norm 118 Art. 157-190, 1991, N. 8 zu Art. 174). Ob vorliegend während der Garantiefrist Mängelrüge erhoben wurde und diese Beweislastregel insoweit anwendbar ist, wurde nicht festgestellt und ist auch nicht erheblich. Denn sie kommt ohnehin nicht zum Tragen, weil die Vorinstanz es als erwiesen erachtete, dass in Bezug auf den zwischen den Parteien abgeschlossenen Werkvertrag kein vertragswidriger Zustand und mithin kein Mangel vorlag.
4.2 Was die Beschwerdeführer unter dem Titel "Verletzung des allgemeinen Grundsatzes, wonach kein Anspruch auf Überwachung besteht", vorbringen, beruht wiederum auf einer vom angefochtenen Urteil abweichenden Sachverhaltsgrundlage und kann daher nicht verfangen. Nach den vorinstanzlichen Feststellungen hatte die Beschwerdegegnerin keine Pflicht zur Planung und Berechnung der Weinkellerkühlung. Da sie mangels vertraglicher Planungspflicht diese nicht verletzt hat und für Planungsfehler nicht verantwortlich gemacht werden kann, rief sie zu ihrer Entlastung keine allfälligen Überwachungsversäumnisse des für die Planung verantwortlichen Ingenieurbüros C._ an. Die Frage, ob sie dies zu ihrer Entlastung hätte wirksam tun können, stellt sich gar nicht.
4.3 <ref-law> sehen die Beschwerdeführer dadurch verletzt, dass die Vorinstanz keine konkrete Mängel verursachende Weisung oder ein anderes Selbstverschulden der Besteller identifiziert, sondern pauschal aus der Existenz eines verantwortlichen Fachplaners auf eine Entlastung des Unternehmers geschlossen habe. Diese Kritik geht ins Leere. Die Vorinstanz hat nicht auf eine Entlastung der Beschwerdegegnerin geschlossen, sondern festgestellt, dass diese keine vertragliche Planungspflicht hatte, also in Bezug auf ihre vertragliche Leistungspflicht kein Werkmangel vorlag. <ref-law> setzt aber das Bestehen eines solchen voraus und kommt daher vorliegend nicht zur Anwendung.
4.4 Die Vorbringen unter dem Titel "Verletzung von Art. 167 SIA-Norm 118" finden in den verbindlichen tatsächlichen Feststellungen der Vorinstanz (<ref-law>) keine Stütze. Die Vorinstanz hat nicht festgestellt, dass die Mängel durch eine von der Beschwerdegegnerin vorgeschlagene Konzeptänderung verursacht sind, sondern durch Fehler in der Planung, für welche die Beschwerdegegnerin jedoch nicht zuständig war. Damit stossen die Ausführungen der Beschwerdeführer, wonach eine von der Beschwerdegegnerin vorgeschlagene Konzeptänderung eine Unternehmervariante gemäss Art. 167 SIA-Norm 167 darstelle, für deren Mängel sie hafte, ins Leere. Mit der in diesem Zusammenhang erhobenen Kritik an den tatsächlichen Annahmen der Vorinstanz sind die Beschwerdeführer ausgeschlossen (vgl. Erwägung 2).
4.5 Die Berufung auf den Grundsatz, wonach eine Haftung des Ingenieurs ohne Einfluss auf die Haftung des Unternehmers bleibe, vermag den Beschwerdeführern nicht zu helfen. Denn die Frage konkurrierender Ansprüche stellt sich erst, wenn mehrere Haftpflichtige für den gleichen Schaden vorhanden sind. Vorliegend ergab das Beweisverfahren aber, dass die Beschwerdegegnerin für Planungsfehler nicht verantwortlich ist.
4.6 Schliesslich ist auch eine Verletzung von <ref-law> nicht ersichtlich. Es trifft wohl zu, dass die Mängelrechte des Bestellers (Wandelung, Minderung, Nachbesserung) kein Verschulden des Unternehmers voraussetzen. Vorausgesetzt ist aber das Vorliegen eines Werkmangels, also eine Abweichung von der vertraglich geforderten Beschaffenheit des Werkes. Ein solcher ist in Bezug auf den Werkvertrag der Parteien nicht festgestellt.
4.7 Gestützt auf den vorinstanzlich festgestellten Sachverhalt ist die Nichtzulassung der Verrechnungsforderung aufgrund der mangelhaften Weinkellerkühlung bundesrechtlich nicht zu beanstanden.
5. Das Bezirksgericht setzte sich mit der Verrechnungsforderung aufgrund der mangelhaften Isolation der Lüftungskanäle in der Weinkellerdecke nicht auseinander, da diesbezüglich die Verrechnung nicht geltend gemacht worden war. Die Beschwerdeführer holten die Verrechnungserklärung im Berufungsverfahren nach, was die Vorinstanz gestützt auf <ref-law>/ZH in Verbindung mit <ref-law>/ZH für grundsätzlich zulässig befand. Vorausgesetzt sei jedoch, so die Vorinstanz, dass die Verrechnungsforderung sofort beweisbar sei (<ref-law>/ZH). Daran fehle es aber. Neben dem Fehlen der sofortigen Beweisbarkeit sei die Verrechnungsforderung auch nicht begründet, weil es an der genügenden Substantiierung mangle.
Die Beschwerdeführer rügen, die Vorinstanz stelle überhöhte Anforderungen an die Substantiierung eines Mängelfolgeschadens. Wie es sich damit verhält, kann offen bleiben. Denn die Beschwerdeführer lassen die Hauptbegründung der Vorinstanz, wonach es für die Zulässigkeit der im Berufungsverfahren nachgeholten Verrechnungserklärung an der sofortigen Beweisbarkeit im Sinne von <ref-law>/ZH fehle, unangefochten. Da diese Begründung das angefochtene Urteil selbständig zu stützen vermag, fehlt das Rechtsschutzinteresse an der Beurteilung der gegen die zusätzliche Begründung erhobenen Rüge und kann in diesem Punkt auf die Beschwerde nicht eingetreten werden (<ref-ruling>).
6. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern auferlegt, unter solidarischer Haftbarkeit.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 5'000.-- zu entschädigen, unter solidarischer Haftbarkeit.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 17. November 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Widmer