Sachverhalt: A. A.A._ und B.A._ (Kläger und Beschwerdeführer) liessen in U._ ein neues Haus bauen. Bauplanerin war die D._ AG. Diese schlug den Klägern die E._ AG mit Sitz in V._ als Fensterlieferantin vor. Die Kläger wollten jedoch einen ortsansässigen Unternehmer berücksichtigen und holten hierzu Offerten ein. Am 4. Februar 2010 reichte der Einzelunternehmer C._ mit Wohnsitz in W._ (Beklagter und Beschwerdegegner) eine Offerte ein. Am 19. Juli 2010 forderte die Bauplanerin Detailschnitte vom Beklagten an. Die Kläger besuchten am 20. Juli 2010 beim Beklagten die Ausstellung und am Tag darauf stellte die F._ AG der Bauplanerin die Fensterschnitte zu. Am 21. September 2010 lieferte der Beklagte die Fenster. Deren Einbau erfolgte durch die Bauplanerin in ihrer Aufrichtehalle. In der Folge stellte der Beklagte den Klägern Rechnung in der Höhe von Fr. 34'000.--. lm Januar 2011 bezogen die Kläger das neue Haus und stellten schon kurze Zeit danach Kondensat und Eisbildung an den Fenstern fest. Mit Schreiben vom 13. April 2012 setzten die Kläger dem Beklagten Nachfrist zur Unterbreitung eines tauglichen Sanierungsvorschlages. In der Folge traten die Kläger mit Schreiben vom 2. Juli 2012 vom Vertrag zurück. B. B.a. Mit Klage vom 13. November 2012 beantragten die Kläger dem Kantonsgericht von Appenzell A.Rh., der Beklagte sei zu verurteilen, den Klägern Fr. 60'000.-- nebst Zins zu 5 % seit dem 11. Juli 2012 zu bezahlen. Sie machten geltend, dass die gelieferten Fenster weder den gesetzlichen Anforderungen noch dem Stand der Technik entsprochen hätten und zudem - da nicht dem bestellten Fenstertyp entsprechend - ein eigentliches aliud darstellten. Sie seien vom Beklagten "getäuscht" worden. Für die Kosten, die ihnen aufgrund des Austauschs dieser Fenster entstanden sind, forderten die Kläger Schadenersatz. Mit Klageantwort vom 15. Februar 2013 beantragte der Beklagte die Abweisung der Klage. Hinsichtlich der geltend gemachten Mängel und der daraus resultierenden Schadenersatzansprüche erhob er die Verjährungseinrede. Er bestritt sowohl die Lieferung eines aliuds als auch eine Täuschung in diesem Zusammenhang. Mit Urteil vom 19. August 2014 wies das Kantonsgericht die Klage ab. Es kam zum Schluss, dass es sich beim gelieferten Fenstertyp nicht um ein aliud handle und auch keine Täuschung vorliege, weshalb lediglich Ansprüche aus allfälligen Werkmängeln in Frage kämen. Diese seien aber verjährt, da auf den vorliegenden Fall die einjährige Verjährungsfrist von Art. 371 Abs. 1 aOR zur Anwendung gelange. B.b. Dagegen legten die Kläger mit Eingabe vom 14. November 2014 beim Obergericht von Appenzell A.Rh. Berufung ein mit dem Antrag, das Urteil des Kantonsgerichts sei aufzuheben und die Klage sei gutzuheissen. Mit Berufungsantwort vom 5. Februar 2015 beantragte der Beklagte die Abweisung der Berufung, soweit Eintreten. Mit Verfügung vom 9. Februar 2015 teilte das Obergericht den Parteien mit, dass kein zweiter Schriftenwechsel und keine Berufungsverhandlung angeordnet werde. Am 7. April 2015 reichten die Kläger unter dem Titel "Freiwillige Eingabe " eine weitere Rechtsschrift ein, in der sie neue Tatsachenbehauptungen aufstellten und als Beweismittel einen neuen Zeugen nannten. Mit Urteil vom 26. Mai 2015 wies das Obergericht die Berufung ab und bestätigte das Urteil des Kantonsgerichts sowohl im Ergebnis als auch in der Begründung. C. Mit Beschwerde in Zivilsachen beantragen die Kläger dem Bundesgericht, das Urteil des Obergerichts sei aufzuheben und die Klage sei gutzuheissen, eventualiter sei die Sache an die Vorinstanz zu neuer Beurteilung zurückzuweisen. Der Beklagte beantragt in seiner Vernehmlassung die Abweisung der Beschwerde, soweit Eintreten. Die Vorinstanz hat auf Vernehmlassung verzichtet. Die Parteien haben Replik, Duplik, Triplik und Quadruplik eingereicht.