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.

Erwägungen:
1. Das angefochtene Urteil des Verwaltungsgerichts ist ein Entscheid einer letzten kantonalen Instanz (<ref-law>). Ihm liegt ein Beschwerdeverfahren zu einer bewilligungspflichtigen Anlage ausserhalb der Bauzone und damit eine öffentlich-rechtliche Angelegenheit zu Grunde. Das Bundesgerichtsgesetz enthält auf dem Gebiet des Bau- und Planungsrechts keinen Ausschlussgrund von der Beschwerde in öffentlich-rechtlichen Angelegenheiten (Art. 82 lit. a und Art. 83 BGG). Als Eigentümer des betroffenen Grundstücks sind die Beschwerdeführer durch das angefochtene Urteil besonders berührt und haben ein schützenswertes Interesse an dessen Aufhebung. Entsprechend sind sie zur Beschwerde legitimiert (<ref-law>). Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass, sodass auf die frist- und formgerecht eingereichte Beschwerde einzutreten ist.
2. Die Beschwerdeführer machen geltend, die Vorinstanz habe ihren Anspruch auf rechtliches Gehör (<ref-law>) verletzt, indem sie die Durchführung eines Augenscheins sowie den Beizug der Akten betreffend die Zonenplanänderung auf der Parzelle Nr. 41'503 abgelehnt habe.
2.1 Gemäss <ref-law> steht den Parteien das rechtliche Gehör zu. Dieses dient einerseits der Klärung des Sachverhalts und stellt anderseits ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht der betroffenen Person, sich vor Erlass eines sie belastenden Entscheids zur Sache, jedenfalls zumindest zum Beweisergebnis äussern zu können, wenn dieses geeignet ist, den Ausgang des Verfahrens zu beeinflussen (<ref-ruling> E. 5.2 S. 236). Der Anspruch auf rechtliches Gehör ist formeller Natur, womit seine Verletzung ungeachtet der materiellen Begründetheit des Rechtsmittels zur Gutheissung der Beschwerde und zur Aufhebung des angefochtenen Entscheids führt (statt vieler: <ref-ruling> E. 2.2 S. 190).
Aus <ref-law> ergibt sich für die Parteien zudem das Recht, Beweisanträge zu stellen, und für die Behörden die Pflicht, rechtzeitig und formgültig angebotene Beweisbegehren entgegenzunehmen und zu berücksichtigen (vgl. <ref-ruling> E. 2b S. 56). Indes kann der Richter das Beweisverfahren schliessen, wenn die Anträge nicht erhebliche Tatsachen betreffen. Gleichermassen kann er Beweisanträge ohne Verletzung des rechtlichen Gehörs ablehnen, wenn er aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener antizipierter Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 5.3 S. 236 f.; <ref-ruling> E. 5.3 S. 148; je mit Hinweisen).
2.2 Das Verwaltungsgericht hat sich im angefochtenen Entscheid mit dem Antrag der Beschwerdeführer auf Durchführung eines Augenscheins befasst und im Wesentlichen dargelegt, es gehe primär um die Klärung von Rechtsfragen. Die relevanten örtlichen Verhältnisse gingen ausreichend klar aus den Akten hervor. Ein Augenschein sei somit nicht notwendig. Diese Ausführungen stellen die Beschwerdeführer nicht in Abrede. Sie machen aber geltend, ein Augenschein wäre für die Beurteilung der Verhältnismässigkeit des Wiederherstellungsbefehls unabdingbar gewesen. Auch sei ein Gesamtbild der Örtlichkeiten erforderlich, um die Zweckmässigkeit einer von ihnen beantragten Zonenplanänderung zu prüfen. Die Kritik der Beschwerdeführer bezieht sich somit im Wesentlichen auf die Verhältnismässigkeitsprüfung durch die Vorinstanz und die Berücksichtigung der von den Beschwerdeführern verlangten Änderung des Zonenplans. Die beanstandete Gehörsverletzung steht in engem Zusammenhang mit der Beurteilung der aufgeworfenen materiellen Rechtsfragen und wird, soweit notwendig, bei deren Behandlung geprüft (E. 3.5 hiernach). Dasselbe gilt für die Frage des Beizugs von Akten einer Zonenplanänderung auf der Parzelle Nr. 41'503 (vgl. E. 3.5 hiernach).
3. In der Sache bringen die Beschwerdeführer vor, die Rückbauverfügung sei unverhältnismässig. Nicht (mehr) bestritten wird, dass das Schwimmbad in der Landwirtschaftszone nicht zonenkonform ist und keine Ausnahmebewilligung im Sinne von Art. 24 ff. RPG erteilt werden kann.
3.1 Der Anordnung der Wiederherstellung des rechtmässigen Zustands kommt massgebendes Gewicht für den ordnungsgemässen Vollzug des Raumplanungsrechts zu. Werden illegal errichtete, dem RPG widersprechende Bauten nicht beseitigt, sondern auf unabsehbare Zeit geduldet, so wird der Grundsatz der Trennung von Bau- und Nichtbaugebiet in Frage gestellt und rechtswidriges Verhalten belohnt. Formell rechtswidrige Bauten, die nachträglich nicht bewilligt werden können, müssen deshalb grundsätzlich beseitigt werden (<ref-ruling> E. 6 S. 364 mit Hinweisen). Bei der Anordnung des Abbruchs bereits erstellter Bauten sind indessen die allgemeinen Prinzipien des Verfassungs- und Verwaltungsrechts zu beachten. Zu ihnen gehören namentlich das öffentliche Interesse und die Verhältnismässigkeit (<ref-law>) sowie der Grundsatz von Treu und Glauben (Art. 5 Abs. 3 und Art. 9 BV). Die Anordnung der Wiederherstellung des rechtmässigen Zustands kann insbesondere unterbleiben, soweit diese unverhältnismässig wäre (vgl. Urteil des Bundesgerichts 1C_397/2007 vom 27. Mai 2008 E. 3.4, in: URP 2008 S. 590). Überdies können Gründe des Vertrauensschutzes der Wiederherstellung entgegenstehen, oder sie kann aufgrund des Zeitablaufs verwirkt sein (<ref-ruling> E. 6-10 S. 365 ff. mit Hinweisen).
3.2 Ob der verfügte Abbruch im öffentlichen Interesse liegt und verhältnismässig ist, prüft das Bundesgericht grundsätzlich frei. Allerdings auferlegt es sich eine gewisse Zurückhaltung, wenn es um die Beurteilung lokaler Gegebenheiten geht, welche die kommunalen und kantonalen Behörden besser kennen und überblicken als das Bundesgericht, und wenn sich ausgesprochene Ermessensfragen stellen (<ref-ruling> E. 2a S. 353, 445 E. 3c S. 451 mit Hinweisen).
3.3 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 (BGE 128 I 1 E. 3e/cc S. 15 mit Hinweisen). 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 die Wiederherstellung entstünde, nicht zu rechtfertigen vermögen (Urteile des Bundesgerichts 1C_397/2007 vom 27. Mai 2008 E. 3.4, in: URP 2008 590; 1A.301/2000 vom 28. Mai 2001 E. 6c S. 30). Grundsätzlich kann sich auch der Bauherr, der nicht gutgläubig gehandelt hat, gegenüber einem Abbruch- oder Wiederherstellungsbefehl auf den Grundsatz der Verhältnismässigkeit berufen. Er 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 Zustands erhöhtes Gewicht beimessen und die dem Bauherrn erwachsenden Nachteile nicht oder nur in verringertem Mass berücksichtigen (<ref-ruling> E. 6.4 S. 40; <ref-ruling> E. 4a S. 255; <ref-ruling> E. 6b S. 224; Urteil 1P.708/2006 vom 13. April 2007 publ. in: ZBl 109/2008 S. 100 E. 5.1).
3.4 Die von den Beschwerdeführern ausserhalb der Bauzone ohne die erforderlichen Bewilligungen vorgenommenen Bauarbeiten verletzen den Grundsatz der Trennung des Baugebiets vom Nichtbaugebiet. Es handelt sich dabei um ein grundlegendes Prinzip des Raumplanungsrechts. Die Abweichung vom Gesetz kann keineswegs als geringfügig eingestuft werden. Zudem können die Beschwerdeführer nicht als gutgläubig gelten, da die Bewilligungspflicht für das Schwimmbecken offensichtlich ist. Der Beschwerdeführer erklärte am Augenschein des Departements für Bau und Umwelt, dass er aus zeitlichen Gründen auf eine vorgängige Baueingabe verzichtet habe. Daraus folgt, dass er über das Bewilligungserfordernis informiert war und sich darüber eigenmächtig hinweggesetzt hat.
Der Auffassung der Beschwerdeführer, mit einer untergeordneten Verschiebung der Zonengrenze bestehe eine verhältnismässige Massnahme, um den rechtswidrigen Zustand nachträglich zu "legalisieren", kann nicht gefolgt werden, da ein solches Vorgehen das öffentliche Interesse an der Einhaltung und Durchsetzung der geltenden Rechtsordnung missachten würde. Würde auf die Beseitigung des Schwimmbeckens verzichtet, so wäre künftig die ordnungsgemässe Durchsetzung der baurechtlichen Vorschriften auch in Bezug auf andere Grundeigentümer, die sich auf den Grundsatz der Gleichbehandlung (<ref-law>) berufen könnten, infrage gestellt. Somit kann der Fortbestand des Beckens nicht toleriert werden. Im vorliegenden Verfahren ist im Übrigen nicht das Gesuch der Beschwerdeführer vom 9. August 2012 zu beurteilen, wonach die für das Schwimmbad beanspruchte Fläche in die Dorfzone aufgenommen werden soll. Vielmehr ist die Frage der Wiederherstellung des rechtmässigen Zustands auf der Grundlage der geltenden Vorschriften und nicht gestützt auf eine hypothetische Änderung der nutzungsplanerischen Grundlagen zu prüfen. Andernfalls würden die Beschwerdeführer besser gestellt als Grundeigentümer, die sich bei der Ausarbeitung eines Bauvorhabens an die geltende Zonenordnung halten und das ordentliche Baubewilligungsverfahren beachten.
3.5 Die Beschwerde muss bereits aus den genannten Gründen abgewiesen werden. Die weiteren Argumente der Beschwerdeführer vermögen an dieser Beurteilung nichts zu ändern. Insbesondere war das Verwaltungsgericht unter den gegebenen Umständen nicht gehalten, selbst einen Augenschein durchzuführen, nachdem bereits das Departement für Bau und Umwelt den Sachverhalt vor Ort abgeklärt hatte und die Akten hinreichend Aufschluss über die tatsächlichen Verhältnisse geben. Auch der Verzicht des Verwaltungsgerichts auf den Beizug der Akten einer Zonenplanänderung auf Parzelle Nr. 41'503 erweist sich unter den vorliegenden Umständen als gerechtfertigt. Die Vorinstanz führt diesbezüglich zutreffend aus, dass es den Beschwerdeführern mit dem Argument der Zonenplanänderung lediglich darum gehe, das formell baurechtswidrige Schwimmbecken nachträglich zu legalisieren. Damit liege eine andere Situation vor als bei Parzelle Nr. 41'503, bei welcher dank einer kleinen Zonenplananpassung eine optimale Eingliederung des damals geplanten Neubaus in das Orts- und Landschaftsbild habe erreicht werden können. Mit der Legalisierung des Schwimmbeckens durch eine nachträgliche Zonenplanänderung werde hingegen offensichtlich keine bessere Situation in ortsbaulicher und landschaftlicher Hinsicht erreicht. Das Bundesgericht hat auch aufgrund der Vorbringen der Beschwerdeführer keinen Anlass, diese Ausführungen der Vorinstanz infrage zu stellen. Die Änderung des Zonenplans im Hinblick auf die Optimierung der Eingliederung eines künftigen Neubaus ist nicht gleich zu behandeln wie eine nachträglich beantragte Zonenplananpassung mit dem Ziel, eigenmächtig erstellte Bauten nachträglich zu legalisieren. Somit liegt auch keine Verletzung des Gleichbehandlungsgebots und des Anspruchs auf rechtliches Gehör vor.
4. Es ergibt sich, dass die Beschwerde abzuweisen ist. Mit dem vorliegenden Urteil wird die Verfügung des Stadtrats Frauenfeld vom 21. September 2010 rechtskräftig. Die Beschwerdeführer haben demnach den ursprünglichen Zustand wie er vor Baubeginn bestand, innert drei Monaten wiederherzustellen.
Bei diesem Ausgang des bundesgerichtlichen Verfahrens sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>). Diese haben dem anwaltlich vertretenen Beschwerdegegner eine angemessene Parteientschädigung unter solidarischer Haftbarkeit auszurichten (Art. 68 Abs. 2 und 4 BGG). Den kantonalen und kommunalen Behörden, die in ihrem amtlichen Wirkungskreis obsiegen, steht keine Parteientschädigung zu (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben dem Verband KVA Thurgau eine Parteientschädigung von insgesamt Fr. 3'000.-- unter solidarischer Haftbarkeit zu bezahlen.
4. Dieses Urteil wird den Parteien, der Stadt Frauenfeld, dem Amt für Raumplanung, dem Departement für Bau und Umwelt sowie dem Verwaltungsgericht des Kantons Thurgau und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 5. Februar 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Haag