Sachverhalt:
A. Am 30. August 1966 erteilte die Kantonale Baukommission des Kantons Wallis dem damaligen Eigentümer des ausserhalb der Bauzone der Einwohnergemeinde (EG) Zermatt gelegenen Grundstücks Nr. xxx, Plan Nr. yyy, die Bewilligung zum Bau eines "Walliser Stadels".
Im November 1998 erwarb Y._ die Liegenschaft und reichte am 9. Juli 1999 bei der EG Zermatt ein Ausnahmegesuch für ein Umbauprojekt ein. Ohne die Baubewilligung abzuwarten, begann er mit den Umbauarbeiten, weshalb die Kantonale Baukommission die Arbeiten am 25. August 1999 einstellen liess. Mit Verfügung vom 19. April 2000 erteilte die Kantonale Baukommission die Bewilligung zum Um- und Anbau des bestehenden Gebäudes sowie zur Nutzung als Restaurant. Nachdem am 4. Mai 2000 die öffentlich-rechtliche Eigentumsbeschränkung des Zweckänderungs- und des Veräusserungsverbots zu Spekulationszwecken im Grundbuch eingetragen worden war, stellte die Kantonale Baukommission die Baubewilligung am 24. Mai 2000 zu.
B. Am 28. Juli 2000 reichte Y._ ein weiteres Baugesuch zum Umbau des Restaurants ein, wobei er insbesondere um die Bewilligung für ein vollständiges Untergeschoss und diverse Fassadenänderungen ersuchte. Y._ begann wiederum, ohne den Baubewilligungsentscheid abzuwarten, mit den Umbauarbeiten. Die Kantonale Baukommission liess deshalb am 22. September 2000 die Arbeiten einstellen. Mit Verfügung vom 6. Februar 2001 verweigerte die Kantonale Baukommission die Baubewilligung mit der Begründung, das Bauvorhaben sei weder zonenkonform noch standortgebunden und komme zudem teilweise ins Waldareal zu stehen. Am 28. Februar 2001 teilte die EG Zermatt mit, dass der Bau, für den die Bewilligung verweigert worden war, erstellt und in Betrieb genommen worden sei.
C. Mit Verfügung vom 10. März 2004 verzichtete die Kantonale Baukommission auf die Wiederherstellung des rechtmässigen Zustands, da diese weder verhältnismässig sei noch im öffentlichen Interesse liege; zugleich verurteilte sie die Bauherrschaft zu einer Busse von Fr. 50'000.--. Gegen diese Verfügung reichte Y._ am 8. April 2004 beim Staatsrat des Kantons Wallis eine Beschwerde ein, welche er jedoch wieder zurückzog, sodass das Verfahren am 17. Februar 2006 abgeschrieben wurde.
D. Mit Kaufvertrag vom 5. Oktober 2004 verpflichtete sich Y._, dem Ehepaar AX._ und BX._ die Parzelle Nr. xxx zum Preis von Fr. 950'000.-- zu verkaufen. Der Notar wurde beauftragt, eine vom Verkäufer zu bezahlende Busse vom Verkaufspreis abzuziehen und diese Busse direkt den zuständigen Behörden zu überweisen. Aufgrund der Eigentumsbeschränkung (vgl. Sachverhalt lit. A. hiervor) verweigerte das Grundbuchamt in der Folge die Eintragung des Kaufvertrags. Gestützt auf den Entscheid des Staatsrats vom 12. Mai 2010 wurden AX._ und BX._ schliesslich am 22. Juli 2010 als neue Eigentümer im Grundbuch eingetragen.
E. Am 17. Mai 2005 forderte die Kantonale Baukommission Y._ auf, ein Baugesuch einzureichen, da gemäss der Mitteilung der EG Zermatt das Restaurant in der Zwischenzeit zu einem Wohnhaus umgebaut worden sei. Am 3. Juni 2005 reichte Y._ ein nachträgliches Baugesuch zur Umnutzung des Restaurants zu Wohnraum ein. Ersucht wurde insbesondere um Bewilligung von zwei Zimmern und sanitären Einrichtungen im Untergeschoss.
F. Nach Durchführung eines Vernehmlassungsverfahrens verweigerte die Kantonale Baukommission mit Verfügung vom 9. Januar 2009 die nachgesuchte Baubewilligung für den Umbau des Restaurants zu Wohnzwecken. Auf die Wiederherstellung des Erdgeschosses in den am 19. April 2000 bewilligten Zustand wurde verzichtet. Hingegen wurde Y._ aufgefordert, den rechtmässigen Zustand insoweit wiederherzustellen, als dass innert sechs Monaten nach Eintritt der Rechtskraft der Verfügung die folgenden Wiederherstellungsarbeiten auszuführen seien:
das Untergeschoss darf bestehen bleiben, jedoch wird die Benutzung zu Wohnzwecken untersagt und die Zimmer sind zurückzubauen, lediglich die Innentreppe wird toleriert;
die Aussentreppe im Norden ist abzubrechen;
die Zugangstüre zum Untergeschoss sowie das danebenliegende Fenster auf der Nordseite sind zuzumauern. Der Aushub an dieser Stelle ist zuzuschütten;
die Sanitäreinrichtungen (Bad, Dusche, WC) im Untergeschoss sind zu entfernen;
der Heizungsraum im Untergeschoss kann als solcher bestehen bleiben;
der Lichtschacht auf der Ostseite und sein Geländer sind abzureissen, das Fenster zuzumauern und der Aushub aufzufüllen;
die Steinterrassen sind auf einen Zugangsweg von 1.20 m Breite zu reduzieren;
die Feuerstellen (Cheminée oder Grill) im Aussenbereich sind zu entfernen;
das Vordach ist auf das Mass laut Bewilligung vom 19. April 2000 zu kürzen;
sämtliche Umgebungsarbeiten sind zurückzubauen und das Gelände ist in einen naturnahen Zustand zurückzuführen."
G. Gegen diese Verfügung erhob Y._ am 2. März 2009 beim Staatsrat Beschwerde. Er machte geltend, dass im Zeitpunkt der Verfügung der Kantonalen Baukommission vom 10. März 2004 (vgl. Sachverhalt lit. C. hiervor) die Umnutzung des Restaurants zu Wohnraum bereits vollzogen gewesen sei, sodass mit der Wiederherstellungsverfügung vom 9. Januar 2009 der Grundsatz der Rechtswirksamkeit von Verwaltungsverfügungen verletzt werde. Das von ihm gestellte Abänderungsgesuch vom 3. Juni 2005 sei deshalb nicht mehr notwendig gewesen. Im Übrigen sei die Wiederherstellung nicht verhältnismässig und verletze den Vertrauensgrundsatz.
Mit Entscheid vom 12. Mai 2010 wies der Staatsrat die Beschwerde ab und erwog, dass die Nutzungsänderung eine Baubewilligung erfordere und keine abgeurteilte Sache vorliege. Aufgrund der baulichen Änderungen komme Art. 24a RPG (SR 700) nicht zur Anwendung. Für ein Bergrestaurant bestehe eine gewisse Standortgebundenheit im Sinne von Art. 24 RPG, was bei einer Wohnnutzung nicht der Fall sei. Angesichts der massiven Abweichung vom Erlaubten sei die verfügte Wiederherstellung verhältnismässig.
H. Mit Eingabe vom 17. Juni 2010 führte Y._ gegen diesen Entscheid Verwaltungsgerichtsbeschwerde ans Kantonsgericht Wallis.
Dieses verfügte am 5. Juli 2010 unter Hinweis auf den Entscheid des Staatsrats vom 12. Mai 2010, wonach die Ehegatten AX._ und BX._ als neue Eigentümer der Parzelle Nr. xxx im Grundbuch einzutragen seien (vgl. Sachverhalt lit. D. hiervor), dass den neuen Eigentümern im Beschwerdeverfahren Parteistellung zukomme. Zugleich setzte es AX._ und BX._ Frist bis zum 6. September 2010 an, um allfällige Rechtsbegehren in dieser Angelegenheit zu stellen. AX._ und BX._ liessen sich in der Folge nicht vernehmen oder vertreten.
Mit Urteil vom 22. Dezember 2010 wies das Kantonsgericht die Beschwerde von Y._ ab. Die Frist zur Wiederherstellung des rechtmässigen Zustandes gemäss der Verfügung der Kantonalen Baukommission vom 9. Januar 2009 setzte das Kantonsgericht auf sechs Monate nach Eintritt der Rechtskraft des vorliegenden Urteils fest.
I. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, eventuell subsidiärer Verfassungsbeschwerde, vom 2. Februar 2011 beantragen die Eigentümer der Liegenschaft, AX._ und BX._, das Urteil des Kantonsgerichts vom 22. Dezember 2010 sei aufzuheben und die Angelegenheit zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
Mit Verfügung vom 28. Februar 2011 erkannte der Präsident der I. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zu.
J. Das Kantonsgericht und der Staatsrat stellen Antrag auf Beschwerdeabweisung. Die Kantonale Baukommission beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Einwohnergemeinde Zermatt verzichtet auf eine Stellungnahme. Y._ beantragt die Gutheissung der Beschwerde. Das Bundesamt für Raumentwicklung ARE reicht eine Stellungnahme ein, verzichtet jedoch auf das Stellen von Anträgen. Die Vernehmlassungen wurden den Beschwerdeführern zur Kenntnisnahme zugestellt.

Erwägungen:
1. Die Beschwerde richtet sich gegen einen kantonal letztinstanzlichen Endentscheid öffentlich-rechtlicher Natur (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG). Ein Ausschlussgrund ist nicht gegeben (<ref-law>). Die Beschwerdeführer hatten im vorinstanzlichen Verfahren Parteistellung (<ref-law>). Als Eigentümer der von der Wiederherstellung betroffenen Liegenschaft sind sie durch das angefochtene Urteil besonders berührt (lit. b) und haben ein schutzwürdiges Interesse an dessen Aufhebung (lit. c). Sie sind daher zur Beschwerdeführung legitimiert. Auf die Beschwerde ist einzutreten. Für die eventualiter erhobene subsidiäre Verfassungsbeschwerde besteht kein Raum (<ref-law>).
2. 2.1 Die Beschwerdeführer rügen eine Verletzung ihres Anspruchs auf rechtliches Gehör im Sinne von <ref-law>. Die Vorinstanz habe sie bereits am 5. Juli 2010 über das laufende Verfahren informiert, obwohl sie erst am 22. Juli 2010 als Eigentümer des Grundstücks im Grundbuch eingetragen worden seien. Die Mitteilung durch die Vorinstanz sei damit verfrüht erfolgt.
2.2 Diese Argumentation ist nicht stichhaltig. Die Beschwerdeführer hatten seit dem Entscheid des Staatsrats vom 12. Mai 2010 Kenntnis davon, dass sie als neue Eigentümer der fraglichen Parzelle im Grundbuch eingetragen werden würden. Dass die Eintragung erst am 22. Juli 2010 erfolgte, fällt nicht entscheidend ins Gewicht, da die den Beschwerdeführern in der Verfügung vom 5. Juli 2010 angesetzte Frist zur Stellungnahme grosszügig bemessen wurde und erst am 6. September 2010 endete. Inwiefern hierdurch die Möglichkeit der Beschwerdeführer, sich zu äussern, eingeschränkt worden sein soll, ist nicht ersichtlich.
3. 3.1 Die Beschwerdeführer rügen eine Verletzung des Willkürverbots gemäss <ref-law>. Sie machen geltend, die Vorinstanz setze sich darüber hinweg, dass eine abgeurteilte Sache vorliege. Zum Zeitpunkt der Verfügung vom 10. März 2004 sei die Umnutzung des Restaurants zu Wohnraum bereits vollzogen gewesen. Diese Entscheidung, wonach auf die Wiederherstellung verzichtet werde, sei mit dem Rückzug der Beschwerde durch Y._ rechtskräftig geworden und sie hätten sich in gutem Glauben darauf verlassen können. Indem die Vorinstanz nun trotzdem die Wiederherstellung verlange, missachte sie zudem das Gebot der Rechtssicherheit und verhalte sich rechtsmissbräuchlich. Die Beschwerdeführer führen weiter aus, da die Umnutzung zum Zeitpunkt der Verfügung vom 10. März 2004 bereits voll zogen gewesen sei, entstünden keine neuen Auswirkungen auf Raum, Erschliessung und Umwelt, weshalb eine Ausnahmebewilligung im Sinne von Art. 24a RPG (Zweckänderungen ohne bauliche Massnahmen ausserhalb der Bauzonen) hätte erteilt werden können. Von den Beschwerdeführern nicht explizit bestritten wird demgegenüber die Verhältnismässigkeit einer allfälligen Wiederherstellung.
3.2 Mit ihrem Vorbringen, wonach mit der Verfügung vom 10. März 2004 auf die Wiederherstellung verzichtet worden sei und insoweit eine abgeurteilte Sache vorliege, übernehmen die Beschwerdeführer die Argumentation von Y._ im vorinstanzlichen Verfahren.
Die Vorinstanz hat in diesem Zusammenhang erwogen, der Gegenstand des Baubewilligungsverfahrens werde durch das Baugesuch bestimmt. Ein nachträgliches Baugesuch sei ausgeschlossen, wenn bereits rechtskräftig über das ordentliche Bauvorhaben entschieden worden sei. Keine Identität von Bauvorhaben bestehe, wenn mit dem neuen Projekt um eine andere Nutzung nachgesucht werde. Inhalt des Baugesuchs von Y._ vom 28. Juli 2000 habe die Nutzung der Liegenschaft als Restaurant gebildet. Y._ habe die geplanten Umbauarbeiten in der Folge ohne Baubewilligung ausgeführt. Die unerlaubte Erstellung des Untergeschosses habe alsdann Gegenstand der Verfügung vom 10. März 2004 gebildet. Bis zu diesem Zeitpunkt sei das Gebäude mithin als Restaurant bewilligt gewesen. Erst mit dem nachträglichen Baugesuch vom 3. Juni 2005 habe Y._ um die Umnutzung des Restaurants zu Wohnraum ersucht. Gemäss den eingereichten Plänen sollten hierzu im Untergeschoss zwei Zimmer sowie sanitäre Anlagen erstellt werden. Eine solche Zweckänderung, welche mit einem wesentlichen Eingriff in die Bausubstanz verbunden sei, sei baubewilligungspflichtig.
Sofern eine Baute wie im zu beurteilenden Fall ohne gültige Bewilligung errichtet worden sei, so sei vor der Anordnung der Wiederherstellung des rechtmässigen Zustands zu prüfen, ob auch eine Abweichung von den einschlägigen materiellen Vorschriften vorliege. Es frage sich daher, ob für die Umnutzung des Restaurants in ein Wohnhaus eine Ausnahmebewilligung erteilt werden könne. Dies sei nicht der Fall. Art. 24c RPG als Konkretisierung der Bestandesgarantie für Bauten ausserhalb der Bauzone greife bei rechtswidrig erstellten oder geänderten Bauten nicht. Eine Bewilligung gemäss Art. 24a RPG falle ebenfalls ausser Betracht, weil diese Bestimmung Ausnahmen bei einer Zweckänderung nur ohne bauliche Massnahmen zulasse; diese Voraussetzungen seien vorliegend offensichtlich nicht gegeben. Sodann sei auch Art. 24b RPG nicht anwendbar, da es nicht um einen Nebenbetrieb zu einem landwirtschaftlichen Gewerbe gehe. Zonenwidrige Bauvorhaben, welche nicht speziell von den Art. 24a - 24d RPG erfasst würden, könnten - sofern sie den diesbezüglichen Anforderungen entsprächen - schliesslich nach Art. 24 RPG bewilligt werden. Eine Ausnahmebewilligung nach Art. 24 RPG setze aber voraus, dass der Zweck der Baute einen Standort ausserhalb der Bauzone erfordere, was hier nicht der Fall sei. Die Baute sei folglich sowohl in formeller als auch in materieller Hinsicht rechts-widrig und nicht bewilligungsfähig.
Im zu beurteilenden Fall erweise sich die Wiederherstellung als verhältnismässig. Y._ habe die Bauarbeiten im Wissen um das Fehlen einer Baubewilligung in Angriff genommen. Zwar könne sich auch der bösgläubige Bauherr auf den Grundsatz der Verhältnismässigkeit berufen, er müsse aber in Kauf nehmen, dass die Behörden aus grundsätzlichen Erwägungen - nämlich zum Schutz der Rechtsgleichheit und der baurechtlichen Ordnung - dem Interesse an der Wiederherstellung des gesetzmässigen Zustandes erhöhtes Gewicht beimessen würden und die dem Bauherrn erwachsenden Nachteile nicht oder nur in verringertem Mass berücksichtigten. Es gehe vorliegend nicht um eine bloss geringfügige Abweichung vom Erlaubten, und die Trennung von Bau-, Landwirtschafts- und Schutzzonen stelle eines der wichtigsten Ziele der Raumplanung dar. Die privaten Vermögensinteressen vermöchten diese gewichtigen öffentlichen Interessen nicht aufzuwiegen. Dem öffentlichen Durchsetzungsinteresse an der bau- und raumplanungsrechtlichen Ordnung komme damit im Ergebnis der Vorrang zu.
3.3 Diese rechtlichen Erwägungen der Vorinstanz sind zutreffend. Da im Verfahren vor Bundesgericht nicht mehr der bisherige Eigentümer Y._, sondern die neuen Eigentümer Beschwerde führen, ist ergänzend Folgendes festzuhalten: Der jeweilige Grundstückeigentümer gilt als Zustandsstörer und haftet stets für Störungen, die von seinem Grundstück ausgehen. Veräussert er sein Grundstück, entsteht beim Rechtsnachfolger eine eigene bauordnungsrechtliche Zustandsverantwortlichkeit. Dabei ist unerheblich, wodurch der polizei-widrige Zustand der Sache verursacht worden ist. Entscheidend ist allein die objektive Tatsache, dass eine Störung vorliegt und die Sache selbst unmittelbar die Gefahren- oder Schadensquelle bildet. Die polizeiliche Verantwortlichkeit setzt weder beim Verhaltens- noch beim Zustandsstörer Schuldfähigkeit oder konkretes (privat- oder strafrechtliches) Verschulden voraus.
Die neuen Eigentümer - hier die Beschwerdeführer - haben sich den bösen Glauben ihres Rechtsvorgängers anrechnen zu lassen und können eine Wiederherstellung nicht mit dem Argument abwenden, sie hätten das Grundstück gutgläubig erworben und vom polizeiwidrigen Zustand nichts gewusst (vgl. zum Ganzen Magdalena Ruoss Fierz, Massnahmen gegen illegales Bauen, Diss. Zürich 1999, S. 79 ff.).
3.4 Mit ihren Ausführungen vermögen die Beschwerdeführer keine Willkür aufzuzeigen. Die Vorinstanz hat willkürfrei festgestellt, dass erst mit dem Baugesuch vom 3. Juni 2005 um die Umnutzung des Restaurants zu Wohnraum ersucht worden ist. Wie die Vorinstanz zutreffend erwogen hat, ist ein solches mit einer Zweckänderung und einem wesentlichen Eingriff in die Bausubstanz verbundenes neues Projekt baubewilligungspflichtig. Aus der Tatsache, dass mit der Verfügung vom 10. März 2004 in Zusammenhang mit der Nutzung der Liegenschaft als Restaurant auf die Wiederherstellung verzichtet worden ist, können die Beschwerdeführer mithin nichts zu ihren Gunsten ableiten. Es liegt insoweit keine abgeurteilte Sache vor, und der Vorinstanz kann weder eine Missachtung des Grundsatzes der Rechtssicherheit noch ein rechtsmissbräuchliches Vorgehen angelastet werden. Da die Umnutzung des Restaurants zu Wohnraum mit baulichen Massnahmen verbunden ist (Erstellen von zwei Zimmern und sanitären Einrichtungen), hat die Vorinstanz schliesslich auch die Möglichkeit der Erteilung einer Ausnahmebewilligung im Sinne von Art. 24a RPG zu Recht verworfen.
4. Die Beschwerde ist abzuweisen. Die Gerichtskosten sind den unterliegenden Beschwerdeführern aufzuerlegen (Art. 66 Abs. 1 und 5 BGG). Die in ihrem amtlichen Wirkungskreis handelnden kantonalen und kommunalen Behörden haben keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Einwohnergemeinde Zermatt, der Kantonalen Baukommission Wallis, dem Staatsrat des Kantons Wallis, dem weiteren Beteiligten, dem Kantonsgericht Wallis, Öffentlichrechtliche Abteilung, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 10. Mai 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Fonjallaz Stohner