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.