Sachverhalt:
A. Das Grundstück Nr. 487 (Grundbuch Gams) befindet sich in der Landwirtschaftszone der Gemeinde Gams. Es war ursprünglich mit einem Wohnhaus (Vers.-Nr. 946), einem Sticklokal (Vers.-Nr. 947) und einer freistehenden Scheune (Vers.-Nr. 945) überbaut. Das Sticklokal wurde 1973 mit dem Wohnhaus vereinigt.
Ende der 70er Jahre erteilte die Gemeinde Gams dem damaligen Grundstückseigentümer zwei Bewilligungen für den Umbau des Wohnhauses (Vers.-Nr. 946), ohne die Zustimmung der zuständigen kantonalen Stelle einzuholen (Bewilligungen vom 18. Mai 1976 und vom 27. August 1979).
Am 16. August 1980 bewilligte der Gemeinderat Gams, wiederum ohne die Zustimmung des Kantons, den Umbau der Scheune (Vers.-Nr. 945). Nach den Bauplänen waren im Erdgeschoss neben dem Keller ein Bügelraum, ein Waschraum und ein WC, im Obergeschoss eine Doppelgarage und ein Arbeitsraum sowie im Dachgeschoss ein durchgehender Abstellraum geplant. Die Scheune sollte über die Süd- und Ostfassade befenstert und neu unterfangen werden. Ausserdem sollte auf der Westseite eine Zufahrt zur Doppelgarage geschaffen werden.
B. Am 7. Mai 1987 wurde das Grundstück Nr. 487 an die in Gams wohnhaften Eheleute X._ verkauft.
Am 17. Februar 2004 reichte Herr X._ ein Baugesuch für die Erweiterung des Wohnzimmers unter Reduktion der Garage, den Einbau eines Specksteinofens und die Anpassung der Befensterung im Gebäude Vers.-Nr. 945 (ehemalige Scheune) ein.
Auf Aufforderung des kantonalen Amts für Raumentwicklung (AREG) reichte die Gemeinde am 7. September 2005 alle früher erteilten Baubewilligungen sowie eine Bestandesaufnahme über den heutigen baulichen Zustand des Gebäudes Vers.-Nr. 945 ein. Danach sind im Erdgeschoss eine Sauna, ein Bad mit WC, ein separates WC und ein Abstellraum bzw. eine Waschküche vorhanden; im Obergeschoss befindet sich neben der Doppelgarage ein Wohn- und Essraum, und das Dachgeschoss wird als Schlafzimmer genutzt.
Am 6. Oktober 2005 stellte das AREG der Gemeinde und Herr X._ einen Verfügungsentwurf zur Stellungnahme zu, weil es nicht nur beabsichtigte, die Zustimmung zum Bauvorhaben zu verweigern, sondern auch, die Gemeinde zum Rückbau der Wohnnutzung in der ehemaligen Scheune (Vers.-Nr. 945) aufzufordern.
Am 4. November 2005 teilte der Rechtsvertreter von Herr X._ dem AREG mit, er teile die Auffassung, dass das Baugesuch nicht bewilligungsfähig sei und nachträglich auch keine Zustimmung zur Baubewilligung vom 16. August 1980 und den seither ohne Bewilligung vollzogenen Umbauten erteilt werden könne. Hingegen stünden der Schutz des guten Glaubens und der Verhältnismässigkeitsgrundsatz einer Wiederherstellung des rechtmässigen Zustands entgegen.
C. Am 7. November 2005 verweigerte das AREG die Zustimmung zur Baubewilligung und die nachträgliche Zustimmung zur Umnutzung der Scheune Vers.-Nr. 945 in ein Wohnhaus und forderte die Gemeinde auf, innert 30 Tagen nach Rechtskraft die Wiederherstellung des rechtmässigen Zustands anzuordnen.
Am 12. Dezember 2005 wies der Gemeinderat Gams das Baugesuch vom 17. Februar 2004 ab und eröffnete die Verfügung des AREG vom 7. November 2005. Nach Rücksprache mit dem AREG sah es vorerst vom Erlass einer Wiederherstellungsverfügung ab, um im Rahmen eines nachträglichen Baubewilligungsverfahrens zu klären, ob vom Gebäude Vers.-Nr. 946 her noch Erweiterungspotenzial bestehe, das für die Scheune Vers.-Nr. 945 genutzt und dort für die nachträgliche Bewilligung von Wohn-Nebenflächen eingesetzt werden könnte.
Mit Verfügung vom 15. Februar 2007 erteilte das AREG die nachträgliche Zustimmung zu den Baubewilligungen des Gemeinderats vom 18. Mai 1976 und 27. August 1979 betreffend Umbau des Wohnhauses Vers.-Nr. 946.
D. Am 11. Mai 2007 verfügte der Gemeinderat Gams, dass sämtliche nach dem 16. August 1980 vorgenommenen Änderungen zurückzubauen seien. Es sei folgender, von der Gemeinde bewilligter Bauzustand herzustellen:
- UG: Keller, Bügelraum, Waschraum, WC
- EG: Doppelgarage, Arbeitsraum
- OG: Abstellraum
Demnach seien namentlich folgende bauliche Änderungen vorzunehmen:
- UG: Ausbau Sauna, Entfernen der elektrischen Leitungen im Sauna- raum
- UG: Demontage Dusche mit Duschkabine
Das Gebäude Vers.-Nr. 945 dürfe nicht für Wohnzwecke genutzt werden. Dies sei als öffentlich-rechtliche Eigentumsbeschränkung im Grundbuch anzumerken. Die künftige Nutzung des Nebengebäudes werde mit Stichproben überprüft.
Zur Begründung führte der Gemeinderat aus, das AREG habe einen weitergehenden Rückbau verlangt, insbesondere die Reduktion der Belichtung im Dachgeschoss. Der Rückbau auf den Stand vor 1980 wäre jedoch unverhältnismässig, weil seit der Erteilung der Baubewilligung (ohne Zustimmung des Kantons) fast 27 Jahre zurückliegen und die Eheleute X._ das Grundstück in gutem Glauben erworben hätten.
E. Gegen diese Verfügung haben die Eheleute X._ am 19. Juni 2007 Rekurs beim Baudepartement des Kantons St. Gallen erhoben, mit dem Begehren, auf eine Wiederherstellung sei vollständig zu verzichten und die Nutzung zu Wohnzwecken sei zu belassen. Das Baudepartement wies den Rekurs am 25. September 2008 ab, soweit es darauf eintrat.
F. Gegen den Rekursentscheid gelangten die Eheleute X._ am 7. Oktober 2008 an das Verwaltungsgericht des Kantons St. Gallen. Dieses wies die Beschwerde am 9. Juli 2009 ab.
G. Gegen den verwaltungsgerichtlichen Entscheid haben die Eheleute X._ am 14. September 2009 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben und auf eine Wiederherstellung sei vollständig zu verzichten; die Nutzung zu Wohnzwecken sei zu belassen.
H. Das Verwaltungsgericht und das Baudepartement des Kantons St. Gallen schliessen auf Abweisung der Beschwerde. Der Gemeinderat Gams hat auf eine Vernehmlassung verzichtet.
I. Am 11. November 2009 bat der Rechtsvertreter der Beschwerdeführer um Einsicht in die kantonalen Akten. Mit Replik vom 17. Dezember 2009 machte er geltend, die Verfügung vom 12. Dezember 2005 sei nur dem früheren Rechtsvertreter der Beschwerdeführer, RA Y._, zugestellt und offenbar nicht an die Beschwerdeführer weitergeleitet worden. Diese Verfügung sei jedenfalls in Wiedererwägung zu ziehen, auch im Hinblick auf die mittlerweile über 30-jährige Nutzung als Wohnhaus.

Erwägungen:
1. Da alle Sachurteilsvoraussetzungen gegeben sind, ist auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten einzutreten.
Streitig sind nur noch der Rückbau von Sauna und Dusche sowie das Verbot der Nutzung der ehemaligen Scheune (Vers.-Nr. 945) zu Wohnzwecken. Alle anderen Um- und Ausbauten wurden entweder nachträglich bewilligt oder werden von den kantonalen Behörden aus Gründen des Vertrauensschutzes toleriert.
2. Die Beschwerdeführer machen zunächst geltend, das Verwaltungsgericht habe zu Unrecht angenommen, dass sie auf die Anfechtung des Verbotes der Nutzung zu Wohnzwecken verzichtet hätten. Zur Begründung führen sie an, die Verfügung des AREG vom 7. November 2005, wie auch diejenige des Gemeinderats vom 12. Dezember 2005, hätten das Rechtsmittel offen gelassen. In der Replik rügen die Beschwerdeführer überdies erstmals, dass die Verfügung vom 12. Dezember 2005 nicht ihnen, sondern ihrem damaligen Rechtsvertreter zugestellt worden sei.
2.1 Mit Verfügung des AREG vom 7. November 2005 (Disp.-Ziff. 1) wurde die Zustimmung zur Umnutzung der Scheune Vers.-Nr. 945 in ein Wohnhaus verweigert. In den Erwägungen (E. 5) führte das AREG aus, dass weder nach altem noch nach neuem (revidierten) Raumplanungsgesetz eine Möglichkeit zur nachträglichen Bewilligung der Scheune als Wohnbaute bestehe; diese Nutzung sei und bleibe formell wie materiell rechtswidrig.
Diese Verfügung wurde dem Rechtsvertreter der Beschwerdeführer als "integraler Bestandteil" der Verfügung der Gemeinde Gams vom 12. Dezember 2005 eröffnet (Disp.-Ziff. 2), die eine Rechtsmittelbelehrung enthielt. Dennoch wurde keine der beiden Verfügungen von den (anwaltlich vertretenen) Beschwerdeführern angefochten.
2.2 Die Beschwerdeführer legen nicht dar, weshalb die Zustellung an ihren damaligen Rechtsvertreter unzulässig gewesen sei. Dies ist auch nicht ersichtlich. Insofern kann offen bleiben, ob auf die erst in der Replik erhobene Rüge überhaupt eingetreten werden kann.
2.3 Das Verwaltungsgericht durfte daher davon ausgehen, dass die Bewilligung zur Umnutzung der Scheune zu Wohnzwecken rechtskräftig verweigert worden sei.
Davon zu unterscheiden ist die Frage, ob die nicht bewilligte, rechtswidrige Wohnnutzung aufgegeben und der rechtmässige Zustand hergestellt werden muss (<ref-ruling> E. 6 S. 35). Diese Frage ist Gegenstand der Verfügung vom 11. Mai 2007, die von den Beschwerdeführern rechtzeitig angefochten wurde. Diese Frage wurde vom Verwaltungsgericht ausführlich behandelt und ist auch Gegenstand des vorliegenden Verfahrens.
3. 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 zudem aus Gründen des Vertrauensschutzes (<ref-law>) ergeben (<ref-ruling> E. 6.3 S. 39 mit Hinweisen).
3.1 Die Vorinstanzen gingen davon aus, dass der genaue Zeitpunkt des Einbaus von Sauna und Dusche wie auch der Wohnnutzung nicht mehr ermittelt werden könne. Im Schätzungsprotokoll vom 29. September 1981 sei keine Sauna und kein Wohnraum aufgeführt worden; die Sauna sei erstmals im Schätzungsprotokoll vom 24. September 1991 erwähnt worden; im Schätzungsprotokoll vom 29. Juni 2001 sei das Gebäude Vers.-Nr. 945 erstmals als "Wohnhaus" bezeichnet worden. Die Beschwerdeführer machen dagegen geltend, Sauna und Dusche seien bereits 1980/1981 erstellt worden; sie gehen davon aus, dass auch die Wohnnutzung zu diesem Zeitpunkt begonnen habe.
Selbst wenn auf das früheste Datum (1980) abgestellt wird, waren zum Zeitpunkt des Erlasses der Wiederstellungsverfügung (2007) noch keine 30 Jahre vergangen.
3.2 Zu prüfen ist daher, ob vorliegend von einer kürzeren Verwirkungsfrist auszugehen ist. Dies ist namentlich dann der Fall, wenn die Baupolizeibehörden zwar vor Ablauf der 30-jährigen Frist einschreiten, den baurechtswidrigen 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 (<ref-ruling> E. 1c S. 124; Entscheid 1P.768/2000 vom 19. September 2001 E. 3a, in: ZBl 103/2002 S. 188; Pra 2002 Nr. 3 S. 9; RDAF 2003 I S. 395).
3.2.1 Die Beschwerdeführer werfen der Gemeinde Gams vor, den Ausbau und Umbau der ehemaligen Scheune zu Wohnzwecken bewusst geduldet zu haben, weil es sich beim früheren Grundstückseigentümer um eine im Dorf geachtete Persönlichkeit und um einen guten Steuerzahler gehandelt habe.
3.2.2 Fest steht, dass die Gemeinde Gams verschiedene Bauvorhaben bewilligte, ohne die bei Bauten in der Landwirtschaftszone erforderliche Zustimmung des Kantons einzuholen. Für alle derart bewilligten bauliche Massnahmen wurde jedoch auf eine Wiederherstellung aus Gründen des Vertrauensschutzes verzichtet. Die Wiederherstellung wird einzig für die ohne Bewilligung der Gemeinde erfolgten baulichen Massnahmen (Einbau einer Sauna und einer Dusche) sowie die ebenfalls nie bewilligte Nutzung zu Wohnzwecken verlangt.
3.2.3 Diese Umbauten und Nutzungen sind - wie die Beschwerdeführer selbst in anderem Zusammenhang vorbringen - nach aussen nicht sichtbar. Ob die Gemeinde dennoch davon Kenntnis hatte, geht aus den Akten nicht hervor. Zwar wurde die Sauna (erstmals) im Schätzungsprotokoll vom 24. September 1991 und die Wohnnutzung der Baute Vers.-Nr. 945 im Schätzungsprotokoll vom 29. Juni 2001 erwähnt. Diese Protokolle wurden jedoch nicht von der für Baubewilligungen zuständigen Baupolizeibehörde aufgenommen.
Unklar ist auch, ob die Gemeinde 1980/1981 eine Bauabnahme durchgeführt hat. Eine Bauabnahme hätte jedoch die widerrechtlichen Umbauten und -nutzungen nur zutage gebracht, wenn diese damals schon vorhanden waren. Dies steht nach dem oben (E. 3.1) Gesagten nicht fest.
Die Frage kann jedoch offen bleiben, wie im Folgenden darzulegen sein wird.
3.3 Auf eine kürzere Verwirkungsfrist kann sich nach der bundesgerichtlichen Rechtsprechung nur berufen, wer selbst im guten Glauben gehandelt hat (<ref-ruling> E. 6.3 S. 39), 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 (<ref-ruling> E. 6 S. 35; <ref-ruling> E. 6a S. 221 ff.; Entscheid 1P.768/2000 vom 19. September 2001 E. 4c, in: ZBl 103/2002 S. 188; Pra 2002 Nr. 3 S. 9; RDAF 2003 I S. 395).
3.3.1 Das Verwaltungsgericht verneinte den guten Glauben der Beschwerdeführer, weil es diesen bei ausreichendem Studium der Baupläne möglich gewesen wäre festzustellen, dass die Wohnnutzung, wie auch Sauna und Dusche, nie bewilligt worden waren.
3.3.2 Die Beschwerdeführer halten dem entgegen, dass sie nicht Adressaten der damaligen Baubewilligung gewesen seien. Die Sauna und die Dusche sowie die Wohnnutzung seien beim Kauf der Liegenschaft durch die Beschwerdeführer bereits vorhanden gewesen. Sie seien daher gutgläubig gewesen und hätten einen stattlichen Kaufpreis für zwei Wohnhäuser entrichtet. Dieser gute Glaube sei zu schützen.
Die Bezeichnung der Bauten in den Schätzungsprotokollen sei unklar und könne den Beschwerdeführern nicht entgegengehalten werden. Diese hätten vielmehr auf den Kaufvertrag vertraut, der vom Grundbuchamt erstellt worden sei. Es sei weltfremd, von Kaufinteressenten zu verlangen, dass sie Abklärungen beim Bauamt vornehmen. Im Übrigen habe auf dem Bauamt der Gemeinde ein solches Chaos geherrscht, dass dieses nicht in der Lage gewesen wäre, ihnen die nötigen Unterlagen auszuhändigen.
3.3.3 Voraussetzung für den Vertrauensschutz gemäss <ref-law> ist das Vorliegen eines Vertrauenstatbestandes (Entscheid 1P.768/2000 vom 19. September 2001 E. 4a, in: ZBl 103/2002 S. 188; Pra 2002 Nr. 3 S. 9; RDAF 2003 I S. 395). Verlangt wird grundsätzlich eine Handlung oder Unterlassung der zuständigen (oder aus zureichenden Gründen für zuständig erachteten) Behörde in einer konkreten Situation.
Im vorliegenden Fall ist nicht ersichtlich, inwiefern die Beschwerdeführer auf eine behördliche Handlung oder Unterlassung vertraut haben: Sie haben vielmehr dem Verkäufer der Liegenschaft vertraut und angenommen, dass alle von diesem vorgenommenen Umbauten und Umnutzungen ordnungsgemäss, mit Bewilligung der zuständigen Behörden, erfolgt waren, ohne dies näher zu überprüfen.
Eine solche Prüfung wäre aber angesichts der Umstände (umgebaute Scheune in der Landwirtschaftszone) geboten und auch zumutbar gewesen. Dabei ist zu berücksichtigen, dass das Kaufobjekt in dem vom Grundbuchamt Gams erstellten Kaufvertrag als "Wohnhaus Nr. 946" und "Garagen mit Nebenräumen Nr. 945" beschrieben wurde; die Baute Nr. 945 wurde also gerade nicht als Wohnraum bezeichnet. Auch das im Grundbuch angemerkte Wohnungszweckentfremdungsverbot bezog sich ausdrücklich nur auf die Wohnbaute Vers.-Nr. 946 und nicht auf die ehemalige Scheune Vers.-Nr. 945. Im Kaufvertrag wird zudem ausdrücklich darauf hingewiesen, dass die Liegenschaft der Landwirtschaftszone zugeteilt ist und alle Baugesuche und Zweckänderungen der Zustimmung der kantonalen Behörde bedürfen.
Die Beschwerdeführer hätten sich entweder beim Bauamt der Gemeinde oder beim kantonalen Baudepartement erkundigen können; denkbar wäre auch gewesen, vom Verkäufer Einsicht in die Baubewilligungen und die Baugesuchspläne zu verlangen. Sie hätten dann bemerkt, dass weder die Nutzung der Baute Vers.-Nr. 945 zu Wohnzwecken noch der Einbau von Sauna und Dusche je bewilligt worden waren.
Unter diesen Umständen haben die kantonalen Instanzen die Gutgläubigkeit der Beschwerdeführer zu Recht verneint. Dagegen wird diesen nicht vorgeworfen, selbst ohne Bewilligung Umbauten und Umnutzungen vorgenommen zu haben. Die dahingehenden Ausführungen der Beschwerdeführer gehen an der Sache vorbei.
3.4 Nach dem Gesagten ist der Ausschluss einer kürzeren Verwirkungsfrist aus bundesrechtlicher Sicht nicht zu beanstanden. Insofern kann - wie schon im Fall <ref-ruling> E. 6.3 S. 39 geschehen - offen bleiben, inwiefern die Verwirkung überhaupt für Bauten ausserhalb der Bauzone gilt.
4. Zu prüfen bleibt die Verhältnismässigkeit des Wiederherstellungsbefehls. Diese wäre zu verneinen, wenn die Abweichung vom Gesetz gering wäre und die berührten allgemeinen Interessen den Schaden, der den Eigentümern durch den Abbruch bzw. das Nutzungsverbot entstünde, nicht zu rechtfertigen vermag (BGE <ref-ruling> E. 6b S. 224).
4.1 Die Beschwerdeführer machen geltend, ihnen entstehe durch das Nutzungsverbot ein schwerer finanzieller Verlust. Hingegen bringe der angeordnete Rückbau nichts für die Trennung von Bau- und Nichtbaugebiet, weil die Liegenschaft weiterhin in der Landwirtschaftszone liege und sich am äusseren Erscheinungsbild der Bauten nichts ändere.
4.2 Das Verwaltungsgericht ging davon aus, dass das öffentliche Interesse an einer strikten Trennung von Bau- und Nichtbaugebiet am besten mit dem vollständigen Rückbau des Gebäudes Vers.-Nr. 945 in eine Scheune durchgesetzt werden könnte. Auf diese Massnahme sei jedoch im Interesse der Beschwerdeführer zu verzichten. Das Verbot einer Nutzung zu Wohnzwecken sowie der Rückbau von Sauna und Dusche seien die mildesten Massnahmen und seien auch im engeren Sinne verhältnismässig.
4.3 Diese Ausführungen sind nicht zu beanstanden. Die widerrechtliche Schaffung von Wohnraum ausserhalb der Bauzonen widerspricht dem Grundsatz der Trennung des Baugebiets vom Nichtbaugebiet und damit einem der wichtigsten Prinzipien des Raumplanungsrechts des Bundes (<ref-ruling> E. 6.4 S. 40 mit Hinweis). Unter diesen Umständen besteht ein öffentliches Interesse an der Wiederherstellung des rechtmässigen Zustands.
Der besonderen Interessenlage der Beschwerdeführer wurde bereits durch einen weitgehenden Verzicht auf Rückbaumassnahmen Rechnung getragen. Die Kosten für den Rückbau von Sauna und Dusche fallen nicht erheblich ins Gewicht. Das Nutzungsverbot zu Wohnzwecken stellt zwar eine erhebliche Beschränkung der Nutzungsbefugnisse der Beschwerdeführer dar. Allerdings haben diese immerhin seit über 20 Jahren von der rechtswidrigen Situation profitiert, indem sie die Scheune zu Wohnzwecken benutzen konnten. Sie haben aber keinen Anspruch darauf, diese rechtswidrige, dem Raumplanungsrecht widersprechende Wohnnutzung auch in Zukunft fortzusetzen.
Insgesamt überwiegt das öffentliche Interesse an der (zumindest teil-weisen) Wiederherstellung des rechtmässigen Zustands. Die angefochtene Verfügung erweist sich somit als verhältnismässig.
5. Nach dem Gesagten ist die Beschwerde abzuweisen. Bei diesem Ausgang des Verfahrens tragen die Beschwerdeführer die Gerichtskosten und haben keinen Anspruch auf eine Parteientschädigung (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Politischen Gemeinde Gams sowie dem Baudepartement und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 11. Februar 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber