Sachverhalt:
A. X._ und Y._ sind je zur Hälfte Miteigentümer der Parzelle Nr. 1536, Rossfall, Urnäsch, auf welcher das Gasthaus "Rossfall" (Assek. Nr. 424) steht. Das Gasthaus verfügt über einen Saaltrakt im nördlichen Gebäudeteil, in welchem seit vielen Jahren die Sennenbälle stattfinden. Dieser Saaltrakt wurde im Jahre 1981 durch eine Gasexplosion stark beschädigt. Beim Wiederaufbau wurden am Saaltrakt hinterlüftete Holzschindelschirme angebracht, welche rasch anfaulten und in der Folge gestützt auf eine Baubewilligung des Planungsamtes des Kantons Appenzell Ausserrhoden vom 1. September 2003 strassen- und wetterseitig gegen Westen und Norden hin durch je einen Eternitschindelschirm ersetzt wurden. Der Holzschindelschirm an der Ostfassade des Saaltrakts blieb unverändert bestehen. Der Südtrakt des Gasthauses mit Gaststube, Wohnung und Terrasse wurde bei der Gasexplosion weniger stark beschädigt. Er weist strassenseitig eine herkömmliche gestemmte Holztäferfassade auf. Auch auf der Südfassade bestand bis zum Jahr 2006 ein herkömmlicher, nicht hinterlüfteter Holzschindelschirm. Die Ostfassade des Südtraktes ist mit Holzschindeln verkleidet. Gegen den Saaltrakt hin geht die Ostfassade in einen gemauerten Fassadenteil (Kreuzfirst) über.
Das Gasthaus Rossfall liegt in der Landwirtschaftszone. Überdies befindet es sich in der kantonalen Landschaftsschutzzone und ist im kantonalen Schutzzonenplan von 1991 als Ganzes als "Kulturobjekt ausserhalb der Bauzone Nr. 1.9" verzeichnet. Dieser von der Baudirektion erlassene kantonale Schutzzonenplan lag vom 3. Juni bis zum 2. Juli 1991 öffentlich auf und wurde in der Folge rechtskräftig.
B. X._ und Y._ ersuchten am 11. Januar 2006 um die Baubewilligung für die Sanierung der Südfassade des Gasthaus- und Wohntraktes der Liegenschaft Rossfall mittels Eternitschindeln. Das Planungsamt des Kantons Appenzell Ausserhoden erteilte am 17. März 2006 gestützt auf Art. 24c RPG (SR 700) und <ref-law> (SR 700.1) die raumplanerische Bewilligung mit der Auflage, dass anstelle der vorgesehenen Eternitschindeln Holzschindeln anzubringen seien. Diesen Entscheid des Planungsamtes fochten die genannten beiden Miteigentümer zusammen mit der Baubewilligung der Baubewilligungskommission Urnäsch vom 21. März 2006, in welcher die genannte Auflage des Planungsamtes bestätigt wurde, beim kantonalen Departement für Bau und Umwelt an. Sie beantragten, es sei ihnen die Verkleidung der Südfassade mit demselben Eternitschiefer zu bewilligen, wie er an der Nord- und Westfassade des wieder aufgebauten Saaltraktes bewilligt worden sei. Anlässlich des am 6. Juni 2006 durchgeführten Augenscheins stellte das Departement für Bau und Umwelt fest, dass die Holzschindeln an der Südfassade entfernt und entgegen der Auflage im angefochtenen Bauentscheid bereits durch Eternitschindeln ersetzt worden sind.
Mit Entscheid vom 15. August 2006 wies das Departement für Bau und Umwelt den Rekurs im Sinne der Erwägungen ab und bestimmte, die Eternitschindeln an der Südfassade des Gasthauses Rossfall seien zu entfernen und innert dreier Monate durch Holzschindeln zu ersetzen.
C. X._ und Y._ zogen diesen Rekursentscheid an das Verwaltungsgericht des Kantons Appenzell Ausserhoden weiter, welches die Beschwerde mit Urteil vom 27. Juni 2007 abwies. Es hielt im Wesentlichen fest, das Departement für Bau und Umwelt habe für die ohne Bewilligung an der Südfassade des Gasthauses Rossfall angebrachte Eternitverkleidung zu Recht die nachträgliche Baubewilligung verweigert. Der widerrechtlich vorgenommene Materialwechsel und die Aufgabe der herkömmlichen Fassadengliederung mit Eck-Pilastern seien mit den für dieses Kulturobjekt in der Landschaftsschutzzone geltenden Schutz- und Gestaltungsbestimmungen unvereinbar. Die angeordnete Wiederherstellung des rechtmässigen Zustands sei rechtlich zulässig und insbesondere auch verhältnismässig.
D. Gegen dieses Urteil des Verwaltungsgerichts führen X._ und Y._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen, das Urteil des Verwaltungsgerichts, der Entscheid des Departements Bau und Umwelt sowie Ziff. 2 des Bauentscheides des kantonalen Planungsamtes seien aufzuheben und das kantonale Planungsamt sei anzuweisen, die Ausführung der Fassadenerneuerung an der Südfassade des Gebäudes Assek. Nr. 424 mit Eternitschindeln zu bewilligen. Eventualiter sei das Urteil des Verwaltungsgerichts vom 27. Juni 2007 aufzuheben und die Sache zur Neubeurteilung an diese Instanz zurückzuweisen.
E. Mit Präsidialverfügung vom 6. Juni 2008 wurde der Beschwerde aufschiebende Wirkung beigelegt.
F. Das Departement Bau und Umwelt beantragt, die Beschwerde sei abzuweisen. Das Verwaltungsgericht ersucht um Abweisung der Beschwerde, soweit darauf einzutreten sei. In weiteren Eingaben halten die Beschwerdeführer, das Departement Bau und Umwelt und das Verwaltungsgericht an ihren Standpunkten fest.

Erwägungen:
1. 1.1 Das angefochtene Urteil des Verwaltungsgerichts ist ein Entscheid einer letzten kantonalen Instanz (Art. 82 lit. a i.V.m. 86 Abs. 1 lit. d BGG). Ihm liegt ein Beschwerdeverfahren über ein Baubegehren und damit eine öffentlich-rechtliche Angelegenheit zu Grunde. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält dazu keinen Ausschlussgrund (<ref-ruling> E. 1.2 S. 251, 400 E. 2.1 S. 404).
1.2 Nicht einzutreten ist auf die Rechtsbegehren der Beschwerdeführer, wonach auch die Entscheide des Departements Bau und Umwelt und des kantonalen Planungsamtes aufzuheben seien. Diese Entscheide sind durch das Urteil des Verwaltungsgerichts ersetzt worden (sog. Devolutiveffekt) und gelten als inhaltlich mitangefochten (vgl. Urteil des Bundesgerichts 1C_267/2007 vom 28. Februar 2008 E. 1.5; <ref-ruling> E. 1 S. 441; <ref-ruling> E. 1c S. 33; je mit Hinweisen).
1.3 Die Beschwerdeführer bestreiten die im angefochtenen Urteil des Verwaltungsgerichts enthaltenen Feststellungen in tatsächlicher und rechtlicher Hinsicht generell und im Einzelnen, soweit sie diese nicht ausdrücklich anerkennen würden. Dieser pauschale Hinweis erfüllt die Begründungsanforderungen von <ref-law> nicht, weshalb im Folgenden darauf nicht einzutreten ist.
1.4 Die Beschwerdeführer sind als Baugesuchsteller mit Blick auf <ref-law> ohne weiteres legitimiert, den vom Verwaltungsgericht bestätigten Bauabschlag sowie die Wiederherstellungsanordnung mit Beschwerde in öffentlich-rechtlichen Angelegenheiten anzufechten. Die übrigen Sachurteilsvoraussetzungen dieses Rechtsmittels sind erfüllt und geben zu keinen weiteren Bemerkungen Anlass. Auf die Beschwerde ist somit einzutreten.
2. 2.1 Die Beschwerdeführer bringen vor, das Verwaltungsgericht habe ihre Stellungnahme vom 7. Mai 2007 bei der Beurteilung im angefochtenen Entscheid ausser Acht gelassen. Dies stelle einen Verfahrensmangel in der Sachverhaltsfeststellung (<ref-law>) sowie eine Verletzung des in <ref-law> verankerten Anspruchs auf rechtliches Gehör dar. Sie legen dar, die Vorinstanz stelle im angefochtenen Urteil fest, sie hätten darauf verzichtet, sich zu den Akten der kantonalen Schutzzonenplanung zu äussern. Das Verwaltungsgericht habe daraus gefolgert, sie hätten diese Planung und die Unterschutzstellung des Gasthauses Rossfall als Kulturobjekt Nr. 1.9 ausdrücklich anerkannt, weshalb für das Gericht kein Anlass bestehe, die Schutzwürdigkeit des fraglichen Objekts zu überprüfen. Diese Ausführungen des Verwaltungsgerichts zeigten, dass es ihre Stellungnahme vom 7. Mai 2007 nicht zur Kenntnis genommen habe.
Das Verwaltungsgericht bestreitet, die Stellungnahme der Beschwerdeführer vom 7. Mai 2007 nicht in seine Beurteilung einbezogen zu haben. Es räumt zwar ein, es sei ihm unter lit. E des angefochtenen Urteils ein redaktionelles Versehen unterlaufen, indem dort festgehalten werde, die Beschwerdeführer hätten darauf verzichtet, zu den Akten der kantonalen Schutzzonenplanung Stellung zu nehmen. Dass die genannte Stellungnahme der Beschwerdeführer vom Gericht gewürdigt worden sei, ergebe sich aus verschiedenen andern Stellen des angefochtenen Urteils. Andernfalls hätte es in Erwägung 2, S. 7/8 nicht zum Schluss kommen können, dass weder Anlass noch Handhabe bestehe, die Schutzwürdigkeit des Gasthauses Rossfall als Kulturobjekt im Sinne von Art 86 Abs. 4 des kantonalen Gesetzes vom 12. Mai 2003 über die Raumplanung und das Baurecht (Baugesetz, BauG, bGS 721.1) zu überprüfen. Das Gericht habe gerade in Anbetracht der Stellungnahme vom 7. Mai 2007 davon ausgehen dürfen, es bestehe kein Anlass, die Schutzwürdigkeit des Gasthauses zu überprüfen. Von einem unmissverständlichen dem Verwaltungsgericht gestellten Antrag auf akzessorische Überprüfung der 1991 erlassenen Schutzzonenplanung könne jedenfalls nicht die Rede sein.
2.2 In der genannten Stellungnahme vom 7. Mai 2007 nehmen die Beschwerdeführer auf Vorkommnisse betreffend die Entstehungsgeschichte der Unterschutzstellung des Gasthauses Rossfall Bezug und kommen zum Schluss, eine eingehende Auseinandersetzung mit dessen Schutzwürdigkeit habe nie stattgefunden. Wörtlich heisst es in diesem Schreiben: "Sollte deshalb - wider Erwarten - die Meinung der Vorinstanz durchdringen, dass Inhalt und Bedeutung des Schutzes des in Frage stehenden Objektes im konkreten Anwendungsfall einer baulichen Änderung nicht weiter in Frage gestellt werden kann, behalten sich die Beschwerdeführer vor, gestützt auf Art. 86 Abs. 4 BauG beim zuständigen Organ die Überprüfung des Schutzzonenplanes hinsichtlich des Gasthauses Rossfall zu beantragen. Hiefür besteht heute noch kein Anlass." In dieser Aussage kann in der Tat kein Antrag auf akzessorische Überprüfung der in Frage stehenden kantonalen Schutzzonenplanung erblickt werden. Eine solche akzessorische Überprüfung wäre nach der Praxis des Bundesgerichts nur in Ausnahmesituationen zulässig (vgl. <ref-ruling> E. 6b S. 105 f.; <ref-ruling> E. 12c S. 346; je mit Hinweisen). Eine solche Ausnahmesituation wird in der Stellungnahme vom 7. Mai 2007 nicht geltend gemacht. Die Erwägungen des angefochtenen Urteils zeigen überdies, dass die Stellungnahme der Beschwerdeführer vom 7. Mai 2007 darin materiell verarbeitet worden ist. Die Rüge der Verweigerung des rechtlichen Gehörs ist deshalb unbegründet.
2.3 Gemäss <ref-law> kann die Feststellung des Sachverhalts nur gerügt werden, wenn sie offensichtlich unrichtig ist. Das Verwaltungsgericht hält in Erwägung 3.1 des angefochtenen Urteils fest, die vorliegend umstrittene Südfassade des in der Landschaftsschutzzone gelegenen Gasthauses Rossfall sei bis 2006 noch mit einem herkömmlichen Holzschindelschirm verkleidet gewesen, wie dies bei einer Nebenfassade eines herkömmlichen Appenzeller Hauses und auch im Falle eines herkömmlichen Gasthauses typisch und weit verbreitet sei. Was die Beschwerdeführer gegen diese für das Bundesgericht grundsätzlich verbindliche Sachverhaltsfeststellung einwenden, lässt diese nicht als offensichtlich unrichtig erscheinen. Ein Blick auf die verschiedenen vor 2006 aufgenommenen Fotos dieser Fassade in den Akten bestätigt dies. Daran ändern auch die Hinweise der Beschwerdeführer auf den baulichen Zustand der Fassade, auf die daran vorgenommenen Veränderungen und Sanierungen sowie auf ihre Einschätzung der Wetterexponiertheit nichts. Diese Hinweise enthalten zudem überwiegend Kritik an der Sachverhaltswürdigung und damit an der materiellen Rechtsanwendung der Schutznormen des kantonalen Baurechts und nicht an der Sachverhaltsfeststellung im Sinne von <ref-law>. Dies trifft auch zu auf die gerügte "sachverhaltsmässige Beurteilung" des Verwaltungsgerichts hinsichtlich der Frage, welches die Haupt- und welches die Nebenfassade des Schutzobjekts sei.
3. 3.1 Materiell bringen die Beschwerdeführer vor, das kantonale Baurecht sei in verschiedenen Punkten verfassungswidrig ausgelegt und angewendet worden. Sie berufen sich insbesondere auf die Art. 5, 9 und 26 BV und beziehen sich vor allem auf die Art. 82 Abs. 2 und 3 BauG, Art. 86 Abs. 3 und 4 BauG sowie auf Art. 112 Abs. 2 BauG. Diese Bestimmungen lauten wie folgt:
Art. 82 (Landschaftsschutzzonen) Abs. 2 und 3 BauG:
2In Ergänzung zu den Gestaltungsbestimmungen von Art. 112 haben Bauten, Anlagen und landschaftsverändernde Massnahmen erhöhten Anforderungen in Bezug auf die Gestaltung, Farbgebung und Einpassung ins Landschaftsbild zu genügen.
3Neubauten, Umbauten und Renovationen haben sich der herkömmlichen Bauart insbesondere in Bezug auf die Gliederung und Verkleidung der Fassaden, die Fensterteilung und die Umgebungsgestaltung anzupassen.
Art. 86 (Natur- und Kulturobjekte) Abs. 3 und 4 BauG:
3Die geschützten Natur- und Kulturobjekte sind in ihrem Charakter und in ihrer schutzwürdigen Substanz langfristig zu erhalten. Die Grundeigentümerinnen und Grundeigentümer sind verpflichtet, sie dem Schutzzweck entsprechend zu pflegen und zu unterhalten.
4Die Schutzwürdigkeit der Natur- und Kulturobjekte ist durch die verfügende Behörde zu überprüfen, sofern sich die Verhältnisse erheblich geändert haben. Die Eigentümerinnen und Eigentümer können von sich aus eine Überprüfung beantragen.
Art. 112 (Schutz des Orts und Landschaftsbildes) Abs. 2 BauG:
2Ausserhalb der Bauzonen haben sich Neubauten sowie Umbauten und Renovationen an traditionellen Gebäuden der herkömmlichen Bauart zumindest in Bezug auf Gebäude- und Dachform sowie Material- und Farbwahl anzupassen und die Umgebung ist möglichst unverändert zu belassen. Untergeordnete Bauteile wie Sitzplätze und dergleichen sind zulässig, soweit damit das traditionelle Erscheinungsbild der Baute erhalten bleibt.
3.2 Das Verwaltungsgericht führt im angefochtenen Urteil aus, alle Bauten und Anlagen hätten sich nach Art. 112 Abs. 1 BauG so in ihre bauliche und landschaftliche Umgebung einzufügen, dass eine gute Gesamtwirkung entstehe und dass sie das Orts-, Quartier- und Landschaftsbild nicht wesentlich beeinträchtigten. Ausserhalb der Bauzonen hätten sich Neubauten sowie Umbauten und Renovationen an traditionellen Gebäuden überdies der herkömmlichen Bauart zumindest in Bezug auf Gebäude- und Dachform sowie Material- und Farbwahl anzupassen und die Umgebung sei möglichst unverändert zu belassen (Art. 112 Abs. 2 BauG). Weil das umstrittene Bauvorhaben ein Gebäude ausserhalb der Bauzone betreffe, müsse die Renovation der Südfassade diesen erhöhten Anforderungen insbesondere auch bezüglich der Materialwahl genügen. Dies gelte umso mehr, als vorliegend eine herkömmliche Holzschindelfassade am Südtrakt ersetzt werden solle bzw. ersetzt worden sei, welche sowohl gegen Westen als auch gegen Osten je direkt an Holzfassaden herkömmlicher Bauart anschliesse. Dazu komme, dass der umstrittene Eternitschindelschirm an einer in der kantonalen Landschaftsschutzzone gemäss Schutzzonenplan 1991 gelegenen Baute anstelle eines herkömmlichen Holzschindelschirms angebracht worden sei. Das Vorhaben habe in Bezug auf Gestaltung, Farbgebung und Einpassung ins Landschaftsbild zusätzlich den hohen Anforderungen von Art. 82 Abs. 2 und 3 BauG zu genügen. Daraus ergebe sich für das vorliegende Vorhaben, dass eine Anpassung der Fassadenverkleidungen an die herkömmliche Bauart zwingend verlangt sei, ohne dass hierfür noch eine besondere Interessenabwägung erfolgen müsse. Die Materialwahl habe den in den Art. 82 Abs. 3 und Art. 112 Abs. 2 BauG enthaltenen strengen Anforderungen zu entsprechen. Dabei sei zu beachten, dass ein herkömmlicher Holzschindelschirm naturgemäss eine beschränkte Lebensdauer aufweise und deshalb im Rahmen der gesetzlichen Unterhaltspflicht auch an Kulturobjekten periodisch zu ersetzen sei (Art. 86 Abs. 3 und Art. 87 Abs. 1 BauG), ohne dass dadurch deren Schutzwürdigkeit in Frage gestellt werden könne.
3.3 Die Beschwerdeführer halten diese Auslegung des kantonalen Rechts für willkürlich (<ref-law>). Sie verstosse überdies gegen die Eigentumsgarantie (<ref-law>) und gegen das Erfordernis des öffentlichen Interesses am staatlichen Handeln (<ref-law>). Was sie zur Begründung dieser Rügen ausführen, vermag nicht zu überzeugen. So kann ihnen insbesondere nicht gefolgt werden, dass die Auffassung des Verwaltungsgerichts willkürlich sein soll, die Art. 82, 86 Abs. 3 und 112 Abs. 2 BauG seien auf Fälle wie den vorliegenden gleichzeitig anwendbar und enthielten Rechtswirkungen, die kumulativ zu beachten seien. Die Schutzwürdigkeit des gesamten Gasthauses Rossfall ist aufgrund der im angefochtenen Urteil verfassungskonform vorgenommenen Beurteilung zweifellos gegeben. Dass sich eine Eternitverkleidung der Südfassade nicht mit den bereits mehrfach erwähnten Schutzvorschriften des kantonalen Rechts vereinbaren lässt, kann ebenfalls nicht als verfassungswidrig bezeichnet werden. Die vom Verwaltungsgericht angewendeten kantonalen Vorschriften schliessen im Hinblick auf die angerufenen Verfassungsbestimmungen nicht aus, für die umstrittene Südfassade einen Holzschindelschirm zu verlangen. Schliesslich steht die Bundesverfassung auch der vom Verwaltungsgericht angeordneten Wiederherstellung des rechtmässigen Zustands, das heisst der Ersetzung der widerrechtlich angebrachten Eternitverkleidung durch einen Holzschindelschirm nicht im Wege. Zur Begründung dieser Folgerungen kann auf die verfassungsrechtlich haltbare Argumentation im angefochtenen Urteil verwiesen werden. Die von den Beschwerdeführern vor Bundesgericht daran geübte Kritik weist weitgehend appellatorische Züge auf und ist insoweit im bundesgerichtlichen Verfahren unbeachtlich.
4. Die Beschwerde ist aus den genannten Gründen abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend sind die Kosten für das bundesgerichtliche Verfahren den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>). Eine Parteientschädigung ist ihnen nicht zuzusprechen (<ref-law>). Das Departement Bau und Umwelt des Kantons Appenzell Ausserrhoden hat ebenfalls keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Baubewilligungskommission Urnäsch, dem Departement Bau und Umwelt des Kantons Appenzell Ausserrhoden sowie dem Verwaltungsgericht von Appenzell Ausserrhoden, 2. Abteilung, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 11. Dezember 2008
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Haag