Sachverhalt: A. Am 26. April 2007 reichte X._ bei der Gemeinde Niederrohrdorf ein nachträgliches Baugesuch für die Bewilligung einer auf der Parzelle Nr. 63 im Lauf des Jahres 2003 erstellten Remise ein. Das Gebäude weist eine Grundfläche von 65,34 m2 (10,8 m x 6,05 m) auf, ist auf allen vier Seiten mit Wänden versehen und mit einem schwach geneigten Pultdach gedeckt. Eine zuvor bestehende Remise wurde 2003 vollständig abgerissen. Die Parzelle Nr. 63 liegt gemäss dem Kulturlandplan der Gemeinde Niederrohrdorf vom 26. November 1999/5. März 2002 in der Landwirtschaftszone mit überlagerter Weilerzone "Holzrüti". Gegen das vom 16. Mai bis zum 5. Juni 2007 öffentlich aufgelegte Baugesuch gingen keine Einsprachen ein. Mit Verfügung vom 18. Juni 2007 wies das Departement Bau, Verkehr und Umwelt (BVU) des Kantons Aargau das Baugesuch ab und setzte für den Rückbau der bereits erstellten Baute eine dreimonatige Frist ab Rechtskraft des Entscheids an. Diese Verfügung wurde X._ vom Gemeinderat Niederrohrdorf mit Beschluss vom 16. Juli 2007 eröffnet. B. In der Folge reichte X._ Beschwerde beim Regierungsrat des Kantons Aargau ein. Er verlangte die Erteilung der ersuchten Baubewilligung und die Aufhebung der Rückbauverfügung. Der Regierungsrat wies die Beschwerde mit Entscheid vom 23. April 2008 ab. Gegen diesen Entscheid erhob X._ Beschwerde beim Verwaltungsgericht des Kantons Aargau. Er beantragte die Aufhebung des angefochtenen Entscheids und verlangte die Feststellung, dass die Baubewilligung für die Renovation und Ersatzbaute der Remise Nr. 14.1 zu erteilen und die Rückbauverfügung aufzuheben sei. Mit Urteil vom 2. März 2009 wies das Verwaltungsgericht die Beschwerde ab. Es erwog, die fragliche Baute könne weder gestützt auf Art. 16a, noch gestützt auf Art. 24 oder 24c RPG bewilligt werden und sei daher materiell rechtswidrig. Die streitige Rückbauanordnung beurteilte es als verhältnismässig. C. Mit Eingabe vom 30. April 2009 erhebt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 ff. BGG). Er beantragt im Wesentlichen die Aufhebung des verwaltungsgerichtlichen Urteils vom 2. März 2009 und die Feststellung, dass die ersatzweise erstellte Remise zonenkonform sei. Ferner sei zu überprüfen, ob nicht der Gemeinderat Niederrohrdorf anstelle des Departements Bau, Verkehr und Umwelt BVU für die Behandlung des nachträglichen Baugesuchs zuständig gewesen wäre. Der Beschwerdeführer rügt sinngemäss eine Verletzung der Rechtsgleichheit (Art. 8 Abs. 1 BV), des Willkürverbots (Art. 9 BV), des Grundsatzes von Treu und Glauben (Art. 9 BV), des Verhältnismässigkeitsprinzips (Art. 5 Abs. 2 und Art. 36 Abs. 3 BV), des Anspruchs auf rechtliches Gehör (Art. 29 Abs. 2 BV) sowie von Bestimmungen des Raumplanungsgesetzes. Zudem macht er geltend, der Sachverhalt sei unrichtig festgestellt worden (Art. 97 Abs. 1 BGG). D. Der Gemeinderat Niederohrdorf hält in seiner Vernehmlassung an seinen bisherigen Erwägungen und Beschlüssen fest, stellt jedoch keinen Antrag. Das Verwaltungsgericht und das Bundesamt für Raumentwicklung verzichten ausdrücklich auf eine Stellungnahme. Vom Regierungsrat und vom Departement Bau, Verkehr und Umwelt sind keine Vernehmlassungen eingegangen. Mit Eingabe vom 28. Juli 2009 liess der Beschwerdeführer dem Bundesgericht unaufgefordert weitere Dokumente zukommen. 