Sachverhalt:
A. Die Kollektivgesellschaft C._, Bauunternehmung führt auf den Parzellen Nr. 621, 622, 623, 660, 715b und 720 der Gemeinde Obergoms (vormals Obergesteln) einen Umschlagplatz und ein Materialdepot. Die Parzelle Nr. 660 ist im Eigentum von B._, die Parzelle Nr. 623 gehört A._, die übrigen der Kollektivgesellschaft. Sämtliche Parzellen befinden sich in der Landwirtschaftszone und in der roten Lawinengefahrenzone.
Am 17. Juni 2008 teilte die kantonale Baupolizei der Bauunternehmung B._ und A._ mit, bei einer Kontrolle sei festgestellt worden, dass ein Abstellplatz für Material und Maschinen errichtet worden sei. Am 12. August 2009 erliess die Kantonale Baukommission drei separate, an A._, B._ und an die Kollektivgesellschaft C._ gerichtete Verfügungen. Danach haben die Genannten innert drei Monaten auf den erwähnten Parzellen den rechtmässigen Zustand wiederherzustellen, indem sie sämtliche Materialien, Maschinen, Container usw. entfernen, die Pflanzendecke wieder herstellen und die Grundstücke wieder ihrem landwirtschaftlichen Nutzen zuführen sowie das Gelände wieder so herrichten, dass es dem natürlichen Geländeverlauf entspricht.
Gegen diese Verfügungen erhoben A._, B._ und die Kollektivgesellschaft C._ am 2. September 2009 beim Staatsrat des Kantons Wallis Beschwerde. Dieser vereinigte die Verfahren und wies die Beschwerden mit Entscheid vom 12. Mai 2010 ab. Ein dagegen ergriffenes Rechtsmittel wurde vom Kantonsgericht Wallis mit Urteil vom 19. November 2010 ebenfalls abgewiesen.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 10. Januar 2011 beantragen A._, B._ und die Kollektivgesellschaft C._ die Aufhebung des Urteils des Kantonsgerichts Wallis.
Das Kantonsgericht und der Staatsrat schliessen auf Abweisung der Beschwerde. Die Kantonale Baukommission beantragt, die Beschwerde sei abzuweisen, soweit darauf überhaupt eingetreten werden könne. Die Gemeinde Obergoms hat sich nicht vernehmen lassen. Das ebenfalls zur Vernehmlassung eingeladene Bundesamt für Raumentwicklung hat auf eine Stellungnahme verzichtet.

Erwägungen:
1. 1.1 Beim angefochtenen Urteil handelt es sich um einen kantonal letztinstanzlichen Entscheid über bau- und planungsgsrechtliche Wiederherstellungsmassnahmen. Dieser Entscheid unterliegt der Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>). Ausnahmegründe im Sinne von <ref-law> sind nicht gegeben. Die Beschwerdeführer sind Adressaten des angefochtenen Entscheids und von der Anordnung des Rückbaus der Deponie in schutzwürdigen Interessen betroffen. Sie sind somit nach <ref-law> zur Beschwerde legitimiert. Auf die Beschwerde ist im Grundsatz einzutreten.
1.2 Die Beschwerdeführer schildern den Sachverhalt aus eigener Sicht, ohne dabei Rügen gegenüber der Sachverhaltsfeststellung der Vorinstanz zu erheben (<ref-law>). Es besteht insofern kein Anlass, vom Sachverhalt abzuweichen, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 und 2 BGG).
2. 2.1 Die Beschwerdeführer kritisieren, die Vorinstanz habe die von ihnen beantragten Beweismittel in willkürlicher Art und Weise abgelehnt und damit <ref-law> sowie den in <ref-law> verankerten Anspruch auf rechtliches Gehör verletzt. Sie hätten unter anderem die Einvernahme der zuständigen früheren Gemeindepräsidenten sowie die Edition der gesamten Akten der Gemeindeverwaltung Obergoms und der Kantonalen Baukommission verlangt. Mittels dieser Anträge hätten sie beweisen wollen, dass für die Materialdeponie eine Baubewilligung aus dem Jahre 1963 bestehe. Sie selbst hätten ja die Parzellen erst 1978 gekauft. Zudem sei die angeordnete Renaturierung faktisch unmöglich, weil an der betreffenden Stelle immer eine Grube bestanden habe und das Land nie landwirtschaftlich verwendet worden sei. Um dies zu beweisen, hätten sie von der Vorinstanz eine Ortsschau verlangt, was aber ebenfalls abgelehnt worden sei.
2.2 Aus dem verfassungsrechtlichen Anspruch auf rechtliches Gehör gemäss <ref-law> ergibt sich für die Parteien das Recht, Beweisanträge zu stellen, und für die Behörden die Pflicht, rechtzeitig und formgültig angebotene Beweisbegehren entgegenzunehmen und zu berücksichtigen. Indessen kann der Richter Beweisanträge ablehnen, wenn er aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener antizipierter Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 5.3 S. 236 f.; <ref-ruling> E. 2b S. 56; je mit Hinweisen).
2.3 Die Beschwerdeführer legten ihrer Beschwerde an das Kantonsgericht einen Brief des früheren Eigentümers bei. Darin führte dieser unter anderem Folgendes aus: "Ich habe diese besagten Parzellen nach Aufgabe des Zeltplatzes 1963 an B._ und A._ ... als Materiallagerplatz vermietet und anschliessend 1978 verkauft." Weiter reichten die Beschwerdeführer Schreiben der Gemeindeverwaltung und zweier früherer Gemeindepräsidenten ein, worin bestätigt wird, dass der Materiallagerplatz seit 1963 bzw. seit mindestens 30 Jahren besteht. Dass eine Baubewilligung erteilt wurde, geht jedoch aus keinem der vier Schreiben hervor. Namentlich im Brief des früheren Eigentümers wäre ein entsprechender Hinweis zu erwarten gewesen, hätte er tatsächlich jemals über eine solche Baubewilligung verfügt. Vor diesem Hintergrund erscheint es nicht als willkürlich, dass das Kantonsgericht die Einvernahme der ehemaligen Gemeindepräsidenten sowie die Edition der gesamten Akten durch die Gemeindeverwaltung Obergoms und der kantonalen Baukommission abgelehnt hat. Dies insbesondere auch deshalb, weil es für die Beschwerdeführer als Grundeigentümer ohne grossen Aufwand hätte möglich sein müssen, selbst bei den staatlichen Archiven um die Einsicht in die behauptete Bewilligung nachzusuchen. Sie machen jedoch nicht geltend, dies überhaupt versucht zu haben. Eine willkürliche antizipierte Beweiswürdigung und eine daraus resultierende Verletzung des rechtlichen Gehörs ist deshalb zu verneinen.
Zur Frage der Art der Renaturierung enthalten die Verfahrensakten eine Reihe von Fotos. Die Vorinstanz führt diesbezüglich aus, die Beschwerdeführer hätten nicht dargelegt, und es sei auch nicht erkennbar, wie mit der beantragten Ortsschau noch etwas hätte bewiesen werden sollen, was sich nicht bereits aus den Akten ergebe. Mit dieser Erwägung setzen sich die Beschwerdeführer in ihrer Beschwerde ans Bundesgericht nicht auseinander. Sie legen nicht dar, weshalb zu erwarten wäre, dass ein Augenschein entscheidende zusätzliche Erkenntnisse liefern würde. Ebenso wenig zeigen sie auf, weshalb es eine vorbestehende Grube unmöglich machen sollte, das Grundstück als Gesamtes wieder seinem landwirtschaftlichen Nutzen zuzuführen, wie es die Wiederherstellungsverfügung der Kantonalen Baukommission verlangt. Das Grundstück "wieder seinem landwirtschaftlichen Nutzen zuzuführen", heisst dabei offensichtlich nicht, dass eine Pflicht zur landwirtschaftlichen Bewirtschaftung begründet würde. Insofern berufen sich die Beschwerdeführer vergeblich darauf, die Parzellen seien auch vor 1963 nicht landwirtschaftlich genutzt worden. Infrage steht vielmehr die Wiederherstellung der Zonenkonformität der in der Landwirtschaftszone liegenden Fläche. Die mangelnde Substanziierung der Rüge hat zur Folge, dass darauf nicht einzutreten ist (<ref-law>).
3. 3.1 Die Beschwerdeführer rügen eine willkürliche Anwendung von Art. 51 Abs. 5 des Baugesetzes des Kantons Wallis vom 8. Februar 1996 (SGS 705.1) und als Folge davon eine Verletzung der Eigentumsgarantie. Art. 51 Abs. 5 Baugesetz hat folgenden Wortlaut:
Nach Ablauf von zehn Jahren, seitdem die Rechtswidrigkeit erkennbar war, kann die Wiederherstellung des rechtmässigen Zustandes nur verlangt werden, wenn zwingende öffentliche Interessen es erfordern. Die Wiederherstellungsverfügung verjährt in jedem Fall nach 30 Jahren seit Beendigung der Bauarbeiten.
Die Beschwerdeführer halten die Feststellung der Vorinstanz, wonach es sich beim Materialdepot um eine Anlage handle, die nicht als fertiggestellt angesehen werden kann, für krass aktenwidrig. Auch kritisieren sie die Erwägung im angefochtenen Entscheid, wonach ein im Jahre 1990 gestelltes und abgelehntes Baugesuch widerlegen soll, dass der Materiallagerplatz seit 1963 bis heute in unveränderter Form besteht. Ein Baugesuch beweise einzig, dass Änderungen geplant wurden, aber nicht, dass solche erfolgten. Gegenstand des Baugesuchs sei zudem nicht die Erweiterung des Materiallagerplatzes, sondern die Ausbeutung von Kies gewesen. Der Materiallagerplatz sei seit 1963 nicht ausgebaut worden und die Wiederherstellungsfrist von 30 Jahren somit abgelaufen.
3.2 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 3.1 S. 153; <ref-ruling> E. 3.1 S. 473 f.; je mit Hinweisen).
Die Beschwerdeführer leiten eine Verletzung der Eigentumsgarantie (<ref-law>) einzig aus der willkürlichen Anwendung von Art. 51 Abs. 5 Baugesetz her. Dass die Verjährungsregelung der kantonalen Bestimmung selbst der Eigentumsgarantie widersprechen sollte, machen sie nicht geltend. Ihre Rüge ist deshalb ausschliesslich unter dem Gesichtspunkt der willkürlichen Anwendung von Art. 51 Abs. 5 Baugesetz zu prüfen.
3.3 Die Vorinstanz begründet ihre Feststellung, dass die Verwirkungsfrist noch nicht abgelaufen ist, auf zweierlei Weise. Zum einen erwägt sie, die Beschwerdeführer hätten im Jahre 1990 ein Gesuch um Vergrösserung der bestehenden Deponie gestellt, woraus folge, dass die Deponie nicht von Anfang an im heutigen Umfang betrieben worden sei. Zum andern nimmt sie den Standpunkt ein, es handle sich beim Materialdepot um eine Anlage, die nicht als beendet angesehen werden könne.
Die Beschwerdeführer bringen vor, es sei krass aktenwidrig zu sagen, dass es sich um eine Anlage handle, die nicht als fertiggestellt angesehen werden könne. Sie tun jedoch nicht dar, zu welchen Aktenstücken die Feststellung im Widerspruch stehen soll (<ref-law>). Aus den bereits erwähnten Schreiben des früheren Grundeigentümers, der Gemeindeverwaltung und zweier früherer Gemeindepräsidenten ergibt sich jedenfalls nichts dergleichen. Diese bestätigen lediglich, dass der Materiallagerplatz im Grundsatz seit 1963 bzw. seit mindestens 30 Jahren besteht, nicht aber, dass er bereits damals in der heutigen Form und im heutigen Umfang betrieben worden sein soll.
Die bei den Akten liegenden Fotos zeigen, dass die Deponie nicht durch feste Einrichtungen wie beispielsweise eine Einfriedung begrenzt wird. Hinsichtlich der Verwendung der Deponie spricht ein vom 23. Dezember 2004 datierender Kurzbericht, welchen die Kollektivgesellschaft C._ ihrer Beschwerde an den Staatsrat beigelegt hatte, von der Lagerung von Baumaterial, Bauschutt, Altautos, Tankanlagen, Ölfässer, Schalungsmaterial usw. Die in den Akten befindlichen Fotos zeigen, dass diese Materialien relativ ungeordnet herumliegen, sich teils zwischen Bäumen und Sträuchern befinden und teils auch schon überwachsen sind. Von einer 1963 erstellten und seither unverändert benutzten, festen Anlage kann augenscheinlich keine Rede sein. Zudem ist es in einem derartigen Fall von vornherein äusserst schwierig, Veränderungen in der Nutzung nachzuweisen. Es erscheint nicht willkürlich, dass die Vorinstanz vor diesem Hintergrund angenommen hat, solange die beschriebene Art der Nutzung anhalte, könne nicht von einer "Beendigung der Bauarbeiten" gesprochen werden, wie sie Art. 51 Abs. 5 Baugesetz für die Auslösung der Verwirkungsfrist voraussetzt. Die betreffende Rüge erweist sich damit als unbegründet und es kann offen bleiben, ob zudem aufgrund des Baugesuchs aus dem Jahr 1990 angenommen werden kann, die Deponie sei erweitert worden.
4. 4.1 Die Beschwerdeführer beanstanden schliesslich die Beurteilung der Verhältnismässigkeit durch das Kantonsgericht. Bis heute seien keinerlei Beeinträchtigungen der Umwelt entstanden. Es habe keine einzige Reklamation von Seiten der Gemeindebehörden, von Umweltverbänden oder von Nachbarn gegeben.
4.2 Die Vorinstanz legt dar, die Beschwerdeführer hätten die Deponie während Jahren ohne Bewilligung betrieben. Sie seien im Bauwesen tätig und es sei ihnen klar gewesen, dass dafür eine Baubewilligung erforderlich sei. Sie würden denn auch selber ausführen, sie hätten "in mehreren Anläufen" versucht, "den Betriebsablauf zu legalisieren". Sie könnten damit nicht als gutgläubig gelten, was für die Prüfung der Verhältnismässigkeit von Bedeutung sei.
Aufgrund der Dimensionen der Deponie könne nicht von einer bloss unbedeutenden Abweichung vom Zulässigen gesprochen werden. Sie verletze den Grundsatz der Trennung des Baugebiets vom Nichtbaugebiet und damit eines der wichtigsten Prinzipien des Raumplanungsrechts des Bundes. Die der Wiederherstellung entgegenstehenden Interessen der Beschwerdeführer seien dagegen ausschliesslich finanzieller Natur. Sie bestünden in der Vermeidung des Aufwands, welcher für die Bereitstellung eines rechtmässigen Deponieplatzes und für den Abtransport des Materials nötig sei. Die Beschwerdeführer würden indessen nicht geltend machen, erhebliche Investitionen in den bestehenden Deponieplatz getätigt zu haben.
4.3 Diese vorinstanzlichen Ausführungen entsprechen der bundesgerichtlichen Rechtsprechung und sind überzeugend (vgl. <ref-ruling> E. 9 S. 368 f. mit Hinweisen). Die pauschale Kritik der Beschwerdeführer (<ref-law>) und die Behauptung, es sei bisher weder zu Beeinträchtigungen der Umwelt noch zu Reklamationen gekommen, vermögen daran nichts zu ändern. Die Rüge erweist sich als unbegründet.
5. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang tragen die Beschwerdeführer die Gerichtskosten (<ref-law>). Sie haben keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Gemeinde Obergoms, der Kantonalen Baukommission Wallis, dem Staatsrat des Kantons Wallis, dem Kantonsgericht Wallis, Öffentlichrechtliche Abteilung, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 7. April 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Fonjallaz Dold