Sachverhalt:
A. Mit Beschluss vom 5. Mai 2008 eröffnete die Baukommission Kloten X._ die Verfügung der Baudirektion des Kantons Zürich vom 3. April 2008, mit welcher ihm eine nachträgliche Rodungsbewilligung bzw. eine nachträgliche Bewilligung zur Auffüllung einer ehemaligen Sandstein-Abbaustelle im Wald verweigert und die Entfernung der Deponie sowie der zu ihr führenden befestigten Zufahrt mit korrekter Entsorgung verlangt wurde.
Den von X._ gegen die Verfügung der Baudirektion erhobenen Rekurs wies die Baurekurskommission IV des Kantons Zürich mit Entscheid vom 17. Dezember 2008 ab.
Diesen Entscheid zog X._ ans Verwaltungsgericht des Kantons Zürich weiter, welches die Beschwerde mit Entscheid vom 28. Januar 2010 abwies.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 9. April 2010 beantragt X._, der Entscheid des Verwaltungsgerichts sei aufzuheben, und die Baudirektion sei anzuweisen, ihm die entsprechende baurechtliche Bewilligung nachträglich zu erteilen. Eventualiter sei der Rückbau der Deponie sowie der befestigten Zufahrtsstrasse, inklusive der jeweiligen Entsorgung, auf Staatskosten vorzunehmen respektive er schadlos zu halten. Subeventualiter sei die Sache zur Durchführung eines Beweisverfahrens an die Vorinstanz zurückzuweisen.
Das Verwaltungsgericht beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Baudirektion stellt Antrag auf Abweisung der Beschwerde. Das Bundesamt für Umwelt reicht eine Vernehmlassung ein, ohne ausdrücklich Anträge zu stellen.
In seiner abschliessenden Stellungnahme hält der Beschwerdeführer an seinen Anträgen fest.
C. Mit Verfügung vom 20. Mai 2010 erkannte der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zu.

Erwägungen:
1. 1.1 Beim angefochtenen Urteil handelt es sich um einen kantonal letztinstanzlichen Entscheid über eine raumplanungsrechtliche Bewilligung für Terrainveränderungen ausserhalb der Bauzone und eine Rodungsbewilligung nach dem Bundesgesetz über den Wald vom 4. Oktober 1991 (Waldgesetz, WaG; SR 921.0). Dieser Entscheid unterliegt der Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>; Art. 34 RPG [SR 700] und <ref-law>). Ausnahmegründe im Sinne von <ref-law> sind nicht gegeben.
Der Beschwerdeführer ist Adressat des angefochtenen Entscheids und von der Verweigerung der Bewilligungen sowie von der Anordnung des Rückbaus der Deponie und der befestigten Zufahrtsstrasse in schutzwürdigen Interessen betroffen. Er ist damit nach <ref-law> zur Beschwerdeführung legitimiert (vgl. <ref-ruling> E. 1.3 S. 252 f.). Auf die Beschwerde ist unter Vorbehalt der nachfolgenden Erwägungen einzutreten.
1.2 Die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung) prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen. Wird eine Verletzung des Willkürverbots geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen dargestellt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.6 S. 130; <ref-ruling> E. 2.1 und 2.2 S. 245 f.).
2. 2.1 Der Beschwerdeführer rügt eine Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>), da sich die Vorinstanz nicht hinreichend mit seinen Vorbringen auseinandergesetzt und seine Beweisanträge (Augenschein, Zeugeneinvernahme etc.) abgewiesen habe. Konsequenz daraus sei eine willkürliche Feststellung des Sachverhalts (<ref-law>).
2. 2.1 Der Beschwerdeführer rügt eine Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>), da sich die Vorinstanz nicht hinreichend mit seinen Vorbringen auseinandergesetzt und seine Beweisanträge (Augenschein, Zeugeneinvernahme etc.) abgewiesen habe. Konsequenz daraus sei eine willkürliche Feststellung des Sachverhalts (<ref-law>).
2.2 2.2.1 Der in <ref-law> gewährleistete Anspruch auf rechtliches Gehör verlangt, dass die Behörde die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt (<ref-ruling> E. 3a S. 51 und 241 E. 2 S. 242). Die Begründungspflicht und der Anspruch auf Begründung sind nicht bereits dadurch verletzt, dass sich die urteilende Behörde nicht mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken (vgl. <ref-ruling> E. 2b S. 102). Ebenso wenig liegt eine Verletzung des rechtlichen Gehörs vor, wenn eine Behörde auf die Abnahme beantragter Beweismittel verzichtet, weil sie aufgrund der bereits abgenommenen Beweise ihre Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, dass ihre Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 3 S. 157; <ref-ruling> E. 2.1 S. 428).
2.2.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. 4.1 S. 133; <ref-ruling> E. 1.2 S. 177).
2.3 Soweit die Rüge der Verletzung des Anspruchs auf rechtliches Gehör den Begründungsanforderungen überhaupt genügt, ist sie nicht stichhaltig. Die Vorinstanz setzt sich im angefochtenen Entscheid mit sämtlichen relevanten Vorbringen des Beschwerdeführers auseinander. Sie konnte sich insbesondere gestützt auf die sich in den Akten befindliche Fotodokumentation ein aussagekräftiges Bild der tatsächlichen Situation machen. Dementsprechend ist sie nicht in Willkür verfallen, indem sie in antizipierter Beweiswürdigung auf weitere Beweismassnahmen verzichtete. Entgegen der Behauptung des Beschwerdeführers hat die Vorinstanz im Übrigen sein Argument, er habe bloss unverschmutztes Aushubmaterial (Erde, Lehm, Steine, Tonsteine und Humus) abgelagert, gewürdigt (vgl. angefochtenes Urteil E. 6). Des Weiteren ist es nicht unhaltbar, dass die Vorinstanz auf eine abgelagerte Menge von 1'500 m3 schloss. So ersuchte der Beschwerdeführer im nachträglichen Baugesuch vom 27. September 2007 um eine Geländeauffüllung im Umfang von 1'500 m3 und gab im Baugesuchsformular ausdrücklich an, dass die Auffüllung bereits erfolgt sei.
3. 3.1 Der Beschwerdeführer macht eine Verletzung des Vertrauensschutzes geltend. Er führt aus, der (angeblich) baurechtswidrige Zustand sei durch die zuständigen Behörden während Jahrzehnten geduldet worden. Zudem habe er aufgrund einer telefonischen Auskunft und eines im Auftrag des kantonalen Amts für Abfall, Wasser, Energie und Luft (AWEL) verfassten Schreibens vom 28. Februar 2005 davon ausgehen dürfen, dass er den Aushub bewilligungsfrei auf dem Nachbargrundstück ablagern dürfe. Aus der Begründung des angefochtenen Entscheids ergebe sich, dass sich das Bewilligungsverfahren äusserst komplex darstelle. Es könne ihm deshalb nicht zum Nachteil gereichen, wenn er sich auf die Auskünfte des AWEL verlassen habe. Schliesslich bestehe kein öffentliches Interesse am Abtransport der abgelagerten Erde, und eine Wiederherstellung des rechtmässigen Zustands wäre auch nicht als verhältnismässig einzustufen.
3.2 Nach der bundesgerichtlichen Rechtsprechung verwirkt der Anspruch der Behörden auf Wiederherstellung des rechtmässigen Zustands im Interesse der Rechtssicherheit grundsätzlich nach 30 Jahren, sofern der Kanton keine kürzeren Verwirkungsfristen vorsieht. Kürzere Verwirkungsfristen können sich jedoch aus Gründen des aus <ref-law> abgeleiteten Vertrauensschutzes ergeben. Dies ist namentlich der Fall, wenn die Baupolizeibehörden zwar vor Ablauf der 30-jährigen Frist einschreiten, den rechtswidrigen Zustand aber über Jahre hinaus duldeten, obschon ihnen die Gesetzwidrigkeit bekannt war oder sie diese bei Anwendung der gebotenen Sorgfalt hätten kennen müssen. Darauf kann sich nach der bundesgerichtlichen Rechtsprechung aber nur berufen, wer selbst in gutem Glauben gehandelt hat, d.h. angenommen hat und (unter Anwendung zumutbarer Sorgfalt) annehmen durfte, die von ihm ausgeübte Nutzung sei rechtmässig bzw. stehe mit der Baubewilligung in Einklang (vgl. zum Ganzen <ref-ruling> E. 6 S. 35 ff.; BGE 1C_556/2009 E. 7).
3.3 Die vom Beschwerdeführer getätigten Ablagerungen im Wald sind unter verschiedenen Gesichtspunkten bewilligungspflichtig. So ist für wesentliche Geländeänderungen, auch soweit sie der Ablagerung von Materialien dienen, eine baurechtliche Bewilligung nach dem kantonalen Gesetz über die Raumplanung und das öffentliche Baurecht vom 7. September 1975 (Planungs- und Baugesetz, PBG/ZH; LS 700.1) erforderlich (vgl. § 309 lit. f PBG/ZH). Gemäss <ref-law> (SR 814.01) dürfen Abfälle nur auf Deponien abgelagert werden. Wer eine Deponie errichten oder betreiben will, braucht eine Bewilligung des Kantons. Sie wird ihm nur erteilt, wenn er nachweist, dass die Deponie nötig ist. In der Bewilligung werden die zur Ablagerung zugelassenen Abfälle umschrieben (<ref-law>). Deponien im Wald benötigen zudem eine Ausnahmebewilligung vom Rodungsverbot (<ref-law>), denn als Rodung gilt die dauernde oder vorübergehende Zweckentfremdung von Waldboden (<ref-law>). Ferner ist eine raumplanerische Ausnahmebewilligung gemäss Art. 24 RPG notwendig.
Entgegen der Argumentation des Beschwerdeführers kann die von ihm angeführte Komplexität des Bewilligungsverfahrens bzw. die Notwendigkeit mehrerer Bewilligungen offensichtlich nicht dazu führen, dass er von der gänzlichen Bewilligungsfreiheit ausgehen konnte. Das Wissen, dass die Erstellung einer betonierten Zufahrt und die umfangreiche Ablagerung von Aushubmaterial im Wald nicht ohne formelles Bewilligungsverfahren ausgeführt werden dürfen, muss auch bei "Laien" vorausgesetzt werden können. Bei der geltenden Rechtslage könnte eine telefonische Auskunft keine hinreichende Vertrauensgrundlage bilden - ganz abgesehen davon, dass die vom Beschwerdeführer behauptete telefonische Zusicherung durch einen Mitarbeiter des AWEL auch nicht erstellt ist. Schliesslich kann der Beschwerdeführer auch aus dem im Auftrag des AWEL verfassten Schreiben vom 28. Februar 2005 nichts zu seinen Gunsten ableiten. Gegenstand des Schreibens bildet die Information über belastete Standorte; eine Bewilligung zur Materialablage wird darin nicht erteilt.
Mangels Handelns in gutem Glauben kann sich der Beschwerdeführer somit nicht mit Erfolg auf die Grundsätze des Vertrauensschutzes berufen. Dementsprechend stellt sich die Frage der Zusprechung von Schadenersatz nicht, und der Beschwerdeführer hat als Verursacher die Kosten der Wiederherstellung des rechtmässigen Zustands zu tragen, sofern diese im öffentlichen Interesse liegt und verhältnismässig ist.
3.4 Dies ist der Fall. Die Trennung des Baugebiets vom Nichtbaugebiet (<ref-ruling> E. 6.4 S. 40 mit Hinweis) und die Beachtung des Grundsatzes, wonach nicht verwertbare Abfälle nur auf dafür vorgesehenen Deponien abgelagert werden dürfen (<ref-law>; Urteil des Bundesgerichts 1C.397/2007 vom 27. Mai 2008 E. 3.4, in: URP 2008 S. 590), stellen gewichtige öffentliche Interessen dar. Gleiches gilt für das Verbot der Zweckentfremdung des Waldbodens (vgl. <ref-law>).
Dem Beschwerdeführer ist eine erhebliche Beeinträchtigung des Waldes durch die Erstellung einer betonierten Zufahrt und die Ablagerung einer grösseren Menge von Aushubmaterial anzulasten. Das gewichtige öffentliche Interesse am Wiederherstellungsbefehl überwiegt die rein wirtschaftlichen Interessen des Beschwerdeführers, zumal dieser nicht in gutem Glauben gehandelt hat. Das Raumplanungs- und Abfallrecht des Bundes kann nur ordnungsgemäss vollzogen werden, wenn in Fällen wie dem vorliegenden die Wiederherstellung des rechtmässigen Zustands angeordnet wird.
4. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Es sind keine Parteientschädigungen zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird dem Beschwerdeführer, der Stadt Kloten, der Baudirektion und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, 3. Kammer, sowie dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 7. Oktober 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Stohner