Sachverhalt: A. Die Y._ AG beabsichtigt, eine auf dem Gebiet der Politischen Gemeinde Bussnang (nachfolgend Gemeinde Bussnang) liegende Lagerhalle zu erweitern. Der bestehende Betrieb der Y._ AG und das Baugrundstück liegen in der Landwirtschaftszone. Auf ein entsprechendes Baugesuch der Y._ AG hin erhoben BX._ und AX._ Einsprache gegen das Bauprojekt. Mit Entscheid vom 3. Oktober 2008 stellte das Amt für Raumplanung des Kantons Thurgau (ARP) fest, dass das Bauvorhaben in der Landwirtschaftszone nicht zonenkonform sei, jedoch unter Einhaltung von Auflagen eine Ausnahmebewilligung erteilt werden könne. B. Mit Entscheid vom 2. April 2009 erklärte das Departement für Bau und Umwelt des Kantons Thurgau (DBU) eine von der Gemeinde Bussnang für die Erweiterung der Lagerhalle erteilte Baubewilligung für nichtig, weil die Gemeinde als Eigentümerin eines Teils des Baugrundstücks zum Entscheid nicht zuständig gewesen sei. Gleichzeitig erteilte das Departement selbst die Baubewilligung für das Bauprojekt (mit Auflagen) und trat auf die Einsprache von BX._ und AX._ nicht ein, weil diese nicht zur Einsprache legitimiert seien. C. Gegen den Entscheid des DBU gelangten BX._ und AX._ mit Beschwerde ans Verwaltungsgericht des Kantons Thurgau. Dieses wies die Beschwerde mit Urteil vom 21. Oktober 2009 ab, weil das DBU die Einsprachelegitimation von BX._ und AX._ zurecht verneint habe. D. Gegen das Urteil des Verwaltungsgerichts haben BX._ und AX._ am 2. Dezember 2009 beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Sie beantragen die Aufhebung des angefochtenen Entscheids sowie der Entscheide des DBU vom 2. April 2009 und des ARP vom 3. Oktober 2008. Die Bau- bzw. Ausnahmebewilligung für die Lagerhalle sei zu verweigern. Eventualiter sei die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen. E. Das Verwaltungsgericht, das DBU, das ARP sowie die Y._ AG schliessen auf Abweisung der Beschwerde. Die Gemeinde Bussnang teilt mit, sie halte an ihrer Stellungnahme zu Handen der Vorinstanz fest. Mit Stellungnahme vom 8. März 2010 hat sich das Bundesamt für Umwelt (BAFU) zur Frage der Legitimation der Beschwerdeführer zur Anfechtung des Bauprojekts geäussert. F. Im weiteren Schriftenwechsel halten die Verfahrensbeteiligten an ihren Anträgen fest.