Sachverhalt: A. X.a._ und X.b._ sind Eigentümer der Parzelle Nr. 41'616 an der Thundorferstrasse in Frauenfeld. Eine Teilfläche dieser Parzelle ist gemäss dem Zonenplan der Stadt Frauenfeld der Dorfzone und die restliche Teilfläche der Landwirtschaftszone zugewiesen. Ohne vorweg um eine Baubewilligung ersucht zu haben, begannen X.a._ und X.b._ mit dem Bau eines Schwimmbeckens auf dem in der Landwirtschaftszone liegenden Teil ihres Grundstücks. Mit Schreiben vom 22. Dezember 2009 hielt das Hochbauamt der Stadt Frauenfeld fest, es sei am 15. Dezember 2009 festgestellt worden, dass auf Parzelle Nr. 41'616 nicht bewilligte Bauarbeiten ausgeführt würden. Anlässlich eines Telefongesprächs vom 16. Dezember 2009 sei das Ehepaar X._ auf diesen Sachverhalt aufmerksam gemacht und es sei ein informeller Baustopp ausgesprochen worden. Die Bauherrschaft habe dem Hochbauamt zugesichert, dass umgehend ein Baugesuch eingereicht werde, damit ein nachträgliches Baubewilligungsverfahren eingeleitet werden könne. In der Folge wurde das Schwimmbecken samt Umgebungsarbeiten fertiggestellt. Am 23. Januar 2010 reichte das Ehepaar X._ ein nachträgliches Baugesuch für die ausgeführte Baute ein. Während der öffentlichen Auflage erhob der Verband KVA Thurgau, Eigentümer der östlich an das Baugrundstück angrenzenden Parzelle Nr. 41'617, Einsprache gegen das Baugesuch. Mit Entscheid vom 27. April 2010 verweigerte das Amt für Raumplanung des Kantons Thurgau (ARP) die nachträgliche Baubewilligung mit der Begründung, dass die Baute weder dem Zweck der Landwirtschaftszone entspreche noch die Voraussetzungen für eine Ausnahmebewilligung nach Art. 24 RPG (SR 700) erfülle. Am 21. September 2010 lehnte der Stadtrat Frauenfeld das Baugesuch aus den gleichen Gründen ab. Er wies die Gesuchsteller an, das Schwimmbecken samt Nebenanlagen und Umgebungsgestaltung vollständig zu entfernen und den ursprünglichen Zustand vor Baubeginn innert drei Monaten ab Rechtskraft seines Entscheids wiederherzustellen. Gegen die Entscheide des ARP und des Stadtrats Frauenfeld erhoben X.a._ und X.b._ am 12. Oktober 2010 Rekurs beim Departement für Bau und Umwelt des Kantons Thurgau (DBU). Dieses wies den Rekurs mit Entscheid vom 28. November 2011 ab. Zur Begründung führte es im Wesentlichen aus, das Schwimmbad entspreche nicht dem Zweck der Landwirtschaftszone und es liege auch kein Ausnahmetatbestand gemäss Art. 24 ff. RPG vor. Das öffentliche Interesse an der Durchsetzung der Bauordnung überwiege die privaten Interessen der Rekurrenten. Die Wiederherstellung des rechtmässigen Zustandes sei auch aus präjudiziellen Gründen angezeigt. Gegen diesen Rekursentscheid gelangten X.a._ und X.b._ an das Verwaltungsgericht des Kantons Thurgau, das die Beschwerde mit Urteil vom 30. Mai 2012 abwies. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 27. August 2012 beantragen X.a._ und X.b._ im Wesentlichen, der Entscheid des Verwaltungsgerichts sei aufzuheben und es sei festzustellen, dass der Rückbau des erstellten Schwimmbades nicht verfügt und dieses daher weiterhin bestehen bleiben und genutzt werden könne. In weiteren Anträgen verlangen sie unter anderem, die Sache sei eventualiter an die Vorinstanz oder an die Stadt Frauenfeld zur erneuten Prüfung im Sinne der Erwägungen (vollständige und richtige Feststellung des Sachverhalts, Gewährung des rechtlichen Gehörs und anschliessende Überprüfung der Verhältnismässigkeit der Anordnung des Rückbaus) zurückzuweisen. Der Verband KVA Thurgau stellt den Antrag, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Stadt Frauenfeld, das DBU und das ARP sowie das Verwaltungsgericht schliessen auf Abweisung der Beschwerde. C. Mit Präsidialverfügung vom 12. Oktober 2012 wurden die Gesuche der Beschwerdeführer um aufschiebende Wirkung und um Sistierung des bundesgerichtlichen Verfahrens abgewiesen.