Sachverhalt:
A. Am 21. September 2006 erstattete die Dienststelle für Wald und Landschaft des Kantons Wallis Strafanzeige gegen X._, weil dieser in einem Privatwald im Gebiet "Milibach" in Fiesch Wald gerodet und die so entstandene freie Fläche mit zugeführtem Aushubmaterial planiert habe. Gestützt auf den am 17. Januar 2007 eingegangenen Polizeibericht eröffnete das Untersuchungsrichteramt Oberwallis am 27. Januar 2007 gegen X._ eine Strafuntersuchung wegen vorsätzlich begangener Rodung ohne Bewilligung. Das Untersuchungsrichteramt holte im Juli 2008 bei der BINA Engineering SA ein Gutachten zur Waldfeststellung ein. Am 11. September 2008 erhob die Regionale Staatsanwaltschaft Oberwallis Anklage und leitete die Akten ans Bezirksgericht Brig, Östlich-Raron und Goms weiter.
Mit Urteil vom 2. April 2009 sprach das Bezirksgericht X._ von den Vorwürfen der Widerhandlung gegen Art. 60 Abs. 1 lit. d und p USG (SR 814.01) und - betreffend die Jahre 2001 und 2002 - der Widerhandlung gegen Art. 42 Abs. 1 lit. a des Bundesgesetzes über den Wald vom 4. Oktober 1991 (Waldgesetz, WaG; SR 921.0) frei. Hingegen sprach es X._ der mehrfachen, vorsätzlich begangenen Rodung ohne Bewilligung in den Jahren 2003 bis 2008 im Sinne von <ref-law> schuldig und verurteilte ihn zu einer Geldstrafe von 30 Tagessätzen zu je Fr. 300.-- (unter Aufschub des Vollzugs bei einer Probezeit von zwei Jahren) und zu einer Busse von Fr. 1'500.--. Das Gericht sah es als erwiesen an, dass durch Absägen von Bäumen, Ausplanieren und Zuführen von Klärschlamm und Humus eine Waldfläche von 1,87 Hektaren (18'700 m2) zu Feldern, inkl. einer Zugangsstrasse, umgestaltet und damit dauernd zweckentfremdet worden war, und dass X._ in seiner Funktion als einzelzeichnungsberechtigtes Verwaltungsratsmitglied der Y._ AG den Auftrag für die Arbeiten erteilt hatte. Dieses Urteil ist unangefochten in Rechtskraft erwachsen.
Mit Verfügung vom 26. Januar 2010 verpflichtete das Departement für Verkehr, Bau und Umwelt des Kantons Wallis X._, die Wiederherstellung des rechtmässigen Zustands des Waldareals bis spätestens Ende September 2010 gemäss speziellen Weisungen auf der Grundlage der Expertise der BINA Engineering SA vom Juli 2008 vorzunehmen und zur Sicherstellung der Wiederherstellungsarbeiten einen Kautionsbetrag von insgesamt Fr. 236'100.-- in den kantonalen Aufforstungsfonds zu bezahlen. Das Departement erwog, neben der strafrechtlichen Erledigung könne wegen der festgestellten Waldschäden die Wiederherstellung des rechtmässigen Zustands und eine Garantieleistung im Sinne von Art. 43 des Vollziehungsreglements zum kantonalen Forstgesetz vom 11. Dezember 1985 (VRFG/VS; SGS/VS 921.100) verfügt werden. Für die Aufforstung werde ein Kautionsbetrag von Fr. 56'100.-- erhoben (Fr. 3.-- pro m2, ausgehend von 18'700 m2). Für den Rückbau der Zufahrtsstrasse und die Entfernung der Bewässerungsanlagen und der illegal abgelagerten Materialien werde eine Kaution von Fr. 180'000.-- eingefordert.
Gegen diese Verfügung erhob X._ am 19. Februar 2010 Beschwerde beim Staatsrat des Kantons Wallis. Dieser wies die Beschwerde mit Entscheid vom 9. Februar 2011 ab.
Die von X._ am 17. März 2011 eingereichte Beschwerde wies das Kantonsgericht Wallis mit Urteil vom 7. Dezember 2011 ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 30. Januar 2012 beantragt X._ dem Bundesgericht, das Urteil des Kantonsgerichts vom 7. Dezember 2011 aufzuheben.
Mit Verfügung vom 23. Februar 2012 hat der Präsident der I. öffentlich-rechtlichen Abteilung der Beschwerde die aufschiebende Wirkung zuerkannt.
Das Kantonsgericht und der Staatsrat beantragen die Abweisung der Beschwerde. Das Bundesamt für Umwelt BAFU hat eine Stellungnahme eingereicht, ohne ausdrücklich Anträge zu stellen. Die Einwohnergemeinde Fiesch hat sich nicht vernehmen lassen. Der Beschwerdeführer hält in seiner Eingabe vom 6. Juni 2012 an seinem Standpunkt fest.

Erwägungen:
1. Das angefochtene Urteil des Kantonsgerichts ist ein Endentscheid einer letzten kantonalen Instanz (Art. 82 lit. a i.V.m. Art. 86 Abs. 1 lit. d und Art. 90 BGG). Ihm liegt ein Beschwerdeverfahren über eine in Zusammenhang mit einer Widerhandlung gegen das WaG ergangene Wiederherstellungsverfügung zugrunde. Dieser Entscheid unterliegt der Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>; <ref-law>). Der Beschwerdeführer hat am vorinstanzlichen Verfahren teilgenommen und ist als zur Wiederherstellung des rechtmässigen Zustands Verpflichteter nach <ref-law> zur Beschwerde legitimiert. Auf die Beschwerde ist einzutreten.
2. Der Beschwerdeführer wurde wegen mehrfacher, vorsätzlich begangener Rodung ohne Bewilligung im Sinne von <ref-law> verurteilt. Als Rodung gilt gemäss <ref-law> die dauernde oder vorübergehende Zweckentfremdung von Waldboden. Nach <ref-law> sind Rodungen verboten. Eine Ausnahmebewilligung darf gemäss <ref-law> nur erteilt werden, wenn der Gesuchsteller nachweist, dass für die Rodung wichtige Gründe bestehen, die das Interesse an der Walderhaltung überwiegen und zudem die folgenden Voraussetzungen erfüllt sind: das Werk, für das gerodet werden soll, muss auf den vorgesehenen Standort angewiesen sein (lit. a); das Werk muss die Voraussetzungen der Raumplanung sachlich erfüllen (lit. b); die Rodung darf zu keiner erheblichen Gefährdung der Umwelt führen (lit. c). Nicht als wichtige Gründe gelten gemäss <ref-law> finanzielle Interessen, wie die möglichst einträgliche Nutzung des Bodens oder die billige Beschaffung von Land für nichtforstliche Zwecke.
Strittig sind vorliegend die Zulässigkeit und der Umfang der angeordneten Wiederherstellung des rechtmässigen Zustands des Waldareals.
3. 3.1 Der Beschwerdeführer rügt eine Verletzung von <ref-law>, da er zu Unrecht als Verhaltensstörer qualifiziert worden sei. Zustands- und auch Verhaltensstörerin sei die Y._ AG und nicht er persönlich. Er führt aus, mit Urteil vom 2. April 2009 des Bezirksgerichts Brig, Östlich-Raron und Goms sei er wegen mehrfacher, vorsätzlich begangener Rodung ohne Bewilligung (<ref-law>) verurteilt worden. Er sei damals einzelzeichnungsberechtigter Verwaltungsrat der Y._ AG gewesen und habe dieses Strafurteil akzeptiert. Per 30. Juli 2009 sei er jedoch aus dem Verwaltungsrat ausgeschlossen worden, und er sei auch nicht Eigentümer der Parzellen, auf welche sich die Wiederherstellungsverfügung beziehe. Ob und in welchem Umfang der Y._ AG allenfalls ein Rückgriffsrecht auf ihn als damaligen Verwaltungsrat zustehe, betreffe das zivilrechtliche Innenverhältnis. Die Wiederherstellungsverfügung gegen ihn zu richten, obwohl er weder Zustands- noch Verhaltensstörer sei, verletze zugleich das Willkürverbot gemäss <ref-law>.
3.2 Die Vorinstanz hat erwogen, ausgehend von der in Rechtskraft erwachsenen Verurteilung des Beschwerdeführers durch das Bezirksgericht Brig, Östlich-Raron und Goms vom 2. April 2009 sei es angebracht, ihn als Verantwortlichen des polizeiwidrigen Zustands zu betrachten, habe der Beschwerdeführer doch ausdrücklich zugegeben, den Auftrag für die Rodung und die Ablagerungen von Klärschlamm an die Y._ AG erteilt zu haben. Die polizeiwidrige Gefahr bzw. Störung sei mithin durch das unter seiner Verantwortung erfolgte Verhalten der Firma verursacht worden. Demzufolge sei nicht zu beanstanden, dass das Departement für Verkehr, Bau und Umwelt den Beschwerdeführer zur Wiederherstellung des rechtmässigen Zustands des Waldareals verpflichtet habe.
3.3 <ref-law>, auf welchen sich der Beschwerdeführer beruft, findet sich systematisch im Kapitel "Abfälle" und dort im Abschnitt "Sanierung belasteter Standorte" und legt fest, dass der Verursacher die Kosten für notwendige Massnahmen zur Untersuchung, Überwachung und Sanierung belasteter Standorte zu tragen hat. Vorliegend handelt es sich zwar um einen belasteten Standort im Sinne des Altlastenrechts, jedoch kommt <ref-law> nicht zur Anwendung, da das Waldrecht als lex specialis vorgeht. Auf die Beantwortung der Frage, ob der Beschwerdeführer zu Recht als Verhaltensstörer qualifiziert worden ist, hat dies jedoch keinen Einfluss.
Störer ist nach herrschender Lehre und Rechtsprechung derjenige, der eine polizeiwidrige Gefahr oder Störung selbst oder durch das unter seiner Verantwortung erfolgende Verhalten Dritter verursacht hat (Verhaltensstörer). Störer ist weiter, wer über die Sache, die den ordnungswidrigen Zustand bewirkt, rechtliche oder tatsächliche Gewalt hat (Zustandsstörer; <ref-ruling> E. 6a S. 70). Bei mehreren Störern können sowohl der Verhaltens- als auch der Zustandsstörer zur Verantwortung gezogen werden. Bei der Auswahl des Pflichtigen steht der zuständigen Behörde ein gewisser Ermessensspielraum zu (BGE 107 la 19 E. 2 S. 23 ff.).
3.4 Die Y._ AG ist als Zustandsstörerin zu qualifizieren, da sie als Eigentümerin die rechtliche und tatsächliche Gewalt über die betroffenen Parzellen hat. Der Beschwerdeführer war einzelzeichnungsberechtigtes Mitglied des Verwaltungsrats der Y._ AG, ist jedoch per 30. Juli 2009 aus dem Verwaltungsrat ausgeschieden und hat damit keine aktuelle Verfügungsmacht über diese Parzellen.
Als Verhaltensstörer kommen sowohl die Firma Y._ AG als auch der Beschwerdeführer in Betracht, denn grundsätzlich haften zwar die juristischen Personen für das Verhalten der für sie handelnden Organe; eine persönliche Haftung der schuldhaft handelnden Organe wird jedoch dadurch nicht ausgeschlossen (<ref-law> analog). Der Beschwerdeführer räumt ein, den Auftrag zur Ausführung der Rodungsarbeiten an seine Arbeiter erteilt zu haben. Obwohl gegen ihn Strafanzeige erhoben wurde, stellte er die Arbeiten nicht ein, sondern liess sie weiterführen (vgl. Urteil des Bezirksgerichts Brig, Östlich-Raron und Goms vom 2. April 2009 S. 5). Damit trägt der Beschwerdeführer eine erhebliche Verantwortung für den polizeiwidrigen Zustand. Dieser Schluss wird auch durch die Organisationsstruktur der Firma Y._ AG (Einzelfirma, vier Kinder des Beschwerdeführers sind Mitarbeiter und Mitglieder des Verwaltungsrats) untermauert. Die Vorinstanz hat daher zu Recht gefolgert, die polizeiwidrige Gefahr bzw. Störung sei durch das unter der Verantwortung des Beschwerdeführers erfolgte Verhalten der Firma verursacht worden. Dass der Beschwerdeführer per 30. Juli 2009 - und damit nach den hier zu beurteilenden Handlungen - aus dem Verwaltungsrat der Y._ AG ausgeschieden ist, ist angesichts der persönlichen Haftung des Beschwerdeführers nicht entscheidend. Den Beschwerdeführer als Verhaltensstörer zu qualifizieren und ihn zur Wiederherstellung des rechtmässigen Zustands des Waldareals zu verpflichten, verletzt nach dem Gesagten kein Bundesrecht.
4. 4.1 Der Beschwerdeführer bringt vor, er sei mit Urteil vom 2. April 2009 des Bezirksgerichts Brig, Östlich-Raron und Goms vom Vorwurf der Widerhandlung gegen Art. 60 Abs. 1 lit. d und p USG freigesprochen worden, da ihm die kantonale Dienststelle für Umweltschutz die entsprechenden Bewilligungen für das Ausplanieren und Zuführen von Klärschlamm und Humus erteilt gehabt habe. Gleichwohl werde in der Wiederherstellungsverfügung des Departements für Verkehr, Bau und Umwelt vom 26. Januar 2010 der Rückbau der Zufahrtsstrasse sowie die Entfernung der Bewässerungsanlagen und des zugeführten Materials (Klärschlamm und Humus) angeordnet und hierfür eine Kaution von Fr. 180'000.-- festgesetzt, was willkürlich sei.
4.2 Gemäss <ref-law> wird mit Freiheitsstrafe bis zu drei Jahren oder Geldstrafe bestraft, wer vorsätzlich mit Stoffen entgegen den Anweisungen so umgeht, dass sie, ihre Folgeprodukte oder Abfälle die Umwelt oder mittelbar den Menschen gefährden können (lit. d mit Hinweis auf <ref-law>), sowie wer vorsätzlich Vorschriften über den Verkehr mit Sonderabfällen verletzt (lit. p mit Hinweis auf <ref-law>).
Mit Urteil vom 2. April 2009 sprach das Bezirksgericht Brig, Östlich-Raron und Goms den Beschwerdeführer in Anwendung des Grundsatzes "in dubio pro reo" vom Vorwurf der Widerhandlung gegen diese beiden Bestimmungen frei, da er über eine Bewilligung zur Klärschlammverarbeitung verfügt habe und nicht erstellt sei, auf welchen Parzellen Ablagerungen in welcher Menge und in welchem Mischverhältnis vorgenommen worden seien.
4.3 In der Wiederherstellungsverfügung vom 26. Januar 2010 führte das Departement für Verkehr, Bau und Umwelt aus, abgesehen von der strafrechtlichen Erledigung könne von der zuständigen Verwaltungs- oder Forstbehörde die Wiederherstellung des rechtmässigen Zustands verfügt werden, falls eine widerrechtliche Handlung festgestellt werde, was hier zweifellos der Fall sei. Die Wiederherstellung beinhalte vorliegend die Wiederbewaldung der gerodeten Flächen, den Rückbau der Zufahrtsstrasse sowie die Entfernung der Bewässerungsanlagen und der illegal abgelagerten Materialien entlang des Gerinnes des Milibachs. Diese Massnahmen seien gemäss der Expertise der BINA Engineering SA vom Juli 2008 sowohl aus Sicherheitsgründen als auch zwecks Wiederherstellung der zerstörten Lebensräume und des Landschaftsbilds zwingend erforderlich.
In der Expertise der BINA Engineering SA vom Juli 2008, auf deren Grundlage die konkret angeordneten Wiederherstellungsmassnahmen basieren, wurde festgehalten, entlang des Milibachs sei Waldareal im Umfang von 1,87 Hektaren gerodet worden. Im Bereich der gerodeten Flächen und des angrenzenden Waldbestands sei viel Material abgelagert worden; die Materialüberdeckung sei an manchen Orten bis zu zwei Meter hoch. Diese Ablagerungen bildeten ein Risiko und müssten aus Sicherheitsgründen beseitigt werden, denn trete der Milibach über die Ufer, so könnte er die Ablagerungen erodieren und das deponierte Material wegspülen. Zudem sei durch die Rodung wertvoller Lebensraum für Pflanzen und Tiere sowie ein attraktives Landschaftsbild stark beeinträchtigt worden, weshalb die gerodeten Flächen wieder bewaldet werden müssten.
4.4 Die unter Bezugnahme auf die (vom Beschwerdeführer inhaltlich nicht bestrittene) Expertise der BINA Engineering SA gemachten Ausführungen des Departements für Verkehr, Bau und Umwelt in der Begründung der Wiederherstellungsverfügung vom 26. Januar 2010 sind korrekt. Der Freispruch von Art. 60 Abs. 1 lit. d und p USG im Strafurteil des Bezirksgerichts Brig, Östlich-Raron und Goms vom 2. April 2009 steht der verwaltungsrechtlichen Wiederherstellung nicht entgegen. Entscheidend ist insoweit, dass der Beschwerdeführer nicht nur für die eigentliche Abholzung, sondern auch für den Bau der Zufahrtsstrasse und der Bewässerungsanlagen sowie für die Ablagerung des Klärschlamms zwingend einer Rodungsbewilligung bedurft hätte.
Gemäss Art. 19 Abs. 1 des hier noch anwendbaren kantonalen Forstgesetzes vom 1. Februar 1985 (in Kraft bis 31. Dezember 2011) ist die Ablagerung von festen oder flüssigen Stoffen im Wald ohne Bewilligung des Kreisforstamts und des Eigentümers verboten. Nach Art. 21 Abs. 1 des kantonalen Vollziehungsreglements zum Forstgesetz ist der Kreisförster zuständig für die Bewilligung von Ablagerungen und Ausbeutungen im Wald bis zu einer Fläche von maximal 200 m2 und Wiederbestockung innert drei Jahren. Grössere oder längerfristige Projekte unterstehen dem Rodungsverfahren.
Im zu beurteilenden Fall handelt es sich um ein "grösseres und längerfristiges Projekt" im Sinne von Art. 21 Abs. 1 des kantonalen Vollziehungsreglements zum Forstgesetz, geht es doch um eine dauernde Zweckentfremdung einer Waldfläche von deutlich über 200 m2. Die Durchführung eines Rodungsverfahrens wäre damit zwingend notwendig gewesen (vgl. zum Ganzen auch Heribert Rausch/Arnold Marti/Alain Griffel, Umweltrecht, 2004, S. 152 ff.; siehe ferner <ref-ruling>). Da kein Rodungsverfahren durchgeführt wurde und die nachträgliche Erteilung einer Ausnahmebewilligung gemäss <ref-law> offensichtlich nicht in Betracht kommt, erweisen sich der Bau der Zufahrtsstrasse und der Bewässerungsanlagen wie auch die Ablagerungen als formell und materiell rechtswidrig, weshalb die Anordnung der Wiederherstellung grundsätzlich zulässig ist.
4.5 Die Wiederherstellung ist auch verhältnismässig:
Vor dem Grundsatz der Verhältnismässigkeit hält ein Grundrechtseingriff stand, wenn er zur Erreichung des angestrebten Ziels geeignet und erforderlich ist und das verfolgte Ziel in einem vernünftigen Verhältnis zu den eingesetzten Mitteln, d.h. den zu seiner Verwirklichung notwendigen Freiheitsbeschränkungen, steht. Ein Wiederherstellungsbefehl erweist sich dann als unverhältnismässig, wenn die Abweichung vom Gesetz gering ist und die berührten allgemeinen Interessen den Schaden, der dem Eigentümer durch den Abbruch entstünde, nicht zu rechtfertigen vermögen (<ref-ruling> E. 6.4 S. 39 f). Grundsätzlich kann sich auch die Bauherrschaft, die nicht gutgläubig gehandelt hat, gegenüber einem Wiederherstellungsbefehl auf den Grundsatz der Verhältnismässigkeit berufen. Sie muss indessen 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 und die der Bauherrschaft erwachsenden Nachteile nicht oder nur in verringertem Mass berücksichtigen (<ref-ruling> E. 6b).
Die ohne Bewilligung gerodete Waldfläche beträgt 1,87 Hektaren, was in etwa der Fläche von zwei Fussballfeldern entspricht. Die Rechtswidrigkeit ist nicht gering, und das öffentliche Interesse an der Wiederherstellung ist dementsprechend gross. Der Beschwerdeführer hat vorsätzlich die widerrechtlichen Arbeiten von der Firma Y._ AG ausführen lassen und handelte damit bösgläubig. Alternativlösungen bieten sich keine an. Es ist demnach nicht zu beanstanden, dass die Vorinstanz das öffentliche Interesse an der Wiederherstellung der waldrechtlichen Ordnung als gewichtiger eingestuft hat als das vermögensrechtliche Interesse des Beschwerdeführers.
5. 5.1 Der Beschwerdeführer rügt, das kantonale Forstgesetz vom 1. Februar 1985 sehe keine Möglichkeit vor, eine Kaution zu erheben. Lediglich in Art. 43 des Vollziehungsreglements zum Forstgesetz sei geregelt, dass der Fehlbare für die Kosten der Wiederherstellungsarbeiten einen entsprechenden Betrag als Kaution in den kantonalen Aufforstungsfonds zu bezahlen habe. Auf Verordnungsstufe aber dürften keine Rechte der Betroffenen eingeschränkt und keine neuen Pflichten auferlegt werden. Mangels expliziter gesetzlicher Grundlage erweise sich die Verpflichtung zur Bezahlung einer Kautionsleistung als unzulässig.
5.2 Art. 45 Abs. 3 des kantonalen Forstgesetzes vom 1. Februar 1985 legt fest, dass die Verpflichtung zu Schadenersatz und zur Wiederherstellung des gesetzlich vorgeschriebenen Zustands vorbehalten bleiben. Gemäss Art. 43 Abs. 1 des Vollziehungsreglements zum Forstgesetz, auf welchen der Beschwerdeführer Bezug nimmt, kann das Departement Wiederherstellungsarbeiten verfügen, wenn diese infolge einer widerrechtlichen Handlung oder Unterlassung nötig sind, und es kann anordnen, dass der Fehlbare für die Kosten dieser Arbeit einen entsprechenden Betrag als Kaution in den kantonalen Aufforstungsfonds zu zahlen hat.
5.3 Mit seiner Argumentation, es fehle an einer hinreichenden gesetzlichen Grundlage, lässt der Beschwerdeführer das Bundesrecht ausser Betracht. Gemäss <ref-law> treffen die kantonalen Behörden umgehend die nötigen Massnahmen zur Beseitigung rechtswidriger Zustände; sie sind zur Erhebung von Kautionen und zur Ersatzvornahme befugt. Die im Vollziehungsreglement zum kantonalen Forstgesetz vorgesehene Möglichkeit, eine Kaution anzuordnen, stützt sich damit auf eine formell-gesetzliche Grundlage im Bundesrecht. Die Berechnung der Kaution als solche wird vom Beschwerdeführer nicht in Frage gestellt.
6. Nach dem Gesagten ist die Beschwerde abzuweisen. Bei diesem Ausgang trägt der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens (<ref-law>). Parteientschädigungen sind keine zuzusprechen (Art. 68 Abs. 1 und 3 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Einwohnergemeinde Fiesch, dem Staatsrat des Kantons Wallis, dem Kantonsgericht Wallis, Öffentlichrechtliche Abteilung, und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 25. Juli 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Stohner