Sachverhalt: A. Am 19./21. August 1996 schlossen A._ und B._ (Kläger, Beschwerdeführer) mit der C2._ AG, der Rechtsvorgängerin der C._ AG (Beklagte, Beschwerdegegnerin), einen Werkvertrag zur Erstellung eines Mehrfamilien-Wohnhauses an der Strasse U._ in Zürich. Nach dem Bezug des Wohnhauses rügten die Kläger gegenüber der Beklagten diverse Mängel. Mit Urteil des Handelsgerichts des Kantons Zürich vom 15. März 2011 (nachfolgend: Kostenvorschussurteil) wurde die Beklagte verpflichtet, den Klägern einen Vorschuss von Fr. 242'740.-- (inklusive 7,6 % MwSt) an die mutmasslichen Kosten der Sanierung der Mängel am Haus der Kläger zu leisten, wobei der Kostenvorschuss zur Finanzierung einerseits einzeln aufgezählter Arbeiten mit den nötigen Folge-/Begleitarbeiten (lit. a-e), entsprechend den angegebenen Kostenanteilen für die einzelnen Mängelsachverhalte, und andererseits zur Begleichung verschiedener einzeln aufgezählter Kosten (Möbelauslagerung, Transport und Einlagerung; Ersatzlogis; Spezialversicherung) dienen müsse (Disp. Ziff. 1). Die Kläger wurden verpflichtet, den Vorschuss ausschliesslich für die Finanzierung der in Ziffer 1 angeführten Nachbesserung zu verwenden und diese innert 18 Monaten vorzunehmen. Bei Säumnis sei der Vorschuss der Beklagten, verzinst zu 5 %, vollumfänglich zurückzuerstatten. Bei Nichtsanierung bestimmter Positionen sei der dafür eingesetzte Kostenanteil (verzinst) zurückzuerstatten (Disp. Ziff. 2). Die Kläger wurden weiter verpflichtet, spätestens 30 Tage nach Ablauf der Frist gemäss Ziffer 2 gegenüber der Beklagten über die Kosten der Nachbesserung abzurechnen und ihr einen allfälligen Überschuss zurückzuerstatten (Disp. Ziff. 3). Im Mehrbetrag wurde die Klage abgewiesen (Disp. Ziff. 4). Die Widerklage wurde ebenfalls abgewiesen (Disp. Ziff. 5). B. Mit Klage vom 19. Juli 2013 beantragten die Kläger dem Handelsgericht des Kantons Zürich, die Beklagte sei zu verpflichten, ihnen Fr. 40'344.35 nebst Zins und Kosten zu bezahlen, und der von der Beklagten erhobene Rechtsvorschlag in diesem Umfang aufzuheben. Zur Begründung brachten sie vor, die tatsächlichen Kosten der durchgeführten Ersatzvornahme zur Beseitigung der Mängel an ihrem Haus hätten um Fr. 40'344.35 den von der Beklagten geleisteten Kostenvorschuss überschritten und seien daher von der Beklagten zu ersetzen. Mit Urteil vom 12. November 2014 wies das Handelsgericht die Klage ab, unter Kosten- und Entschädigungsfolge zu Lasten der Kläger. C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer dem Bundesgericht im Wesentlichen, das Urteil des Handelsgerichts sei aufzuheben und ihre Klage gutzuheissen. Die Beschwerdegegnerin trägt auf kostenfällige Abweisung der Beschwerde an. Das Handelsgericht hat auf eine Vernehmlassung verzichtet.