Sachverhalt: A. A.X._ und B.X._ sind u.a. Eigentümer des Grundstücks Nr. 573N (Grundbuch Nesslau-Krummenau-Stein) in Krummenau. Darauf befinden sich mehrere Gebäude, u.a. auch ihr Wohnhaus. Die Parzelle liegt in der zweigeschossigen Kernzone. Daneben gehören den beiden die weiter westlich gelegenen Grundstücke Nrn. 563N (Landwirtschaftszone) und 564N (Wohn-Gewerbezone WG2 und Landwirtschaftszone). Der nicht in der Landwirtschaftszone liegende Teil der letztgenannten Parzelle wurde an die Sportbahn Krummenau-Wolzenalp AG vermietet und wird von dieser als Parkplatz für die anreisenden Skitouristen genutzt. Südwestlich des Grundstücks Nr. 573N, getrennt durch die Kammernstrasse, befindet sich ein Teil des landwirtschaftlichen Gewerbebetriebs von C._ (Nr. 557N). Anfangs des Jahrs 2009 intervenierten A.X._ und B.X._ bei der Gemeinde Nesslau-Krummenau gegen die Nutzung dieses Grundstücks als Parkfeld für Skitouristen und Kunden der Krummenau-Wolzenalp-Bahn. Nachdem unter den Beteiligten keine allseits befriedigende Lösung gefunden werden konnte, forderten A.X._ und B.X._ die Politische Gemeinde Nesslau-Krummenau mit Schreiben vom 26. Juli 2009 auf, bis 15. September 2009 ein Bewilligungsverfahren für die Nutzung des Grundstücks Nr. 557N als Parkplatz einzuleiten. Mit Schreiben vom 11. September 2009 teilte die Adressatin mit, es bestehe aus ihrer Sicht kein Grund für die Einleitung eines Baubewilligungsverfahrens, da die fragliche Fläche landwirtschaftlich genutzt werde und das Parkplatzproblem Krümmenswil somit während der Vegetationsperiode nicht bestehe. Das vorübergehende Parkieren von Fahrzeugen auf Wiesen sei im Übrigen aus ästhetischen Gründen kaum zu beanstanden, die Zustimmung der Grundeigentümer vorausgesetzt. B. Daraufhin reichten A.X._ und B.X._ am 9. Oktober 2009 wie angekündigt Rechtsverweigerungsbeschwerde und Anzeige beim kantonalen Baudepartement ein. Sie verlangten im Wesentlichen, die Gemeinde sei anzuweisen, für die Umnutzung des landwirtschaftlichen Grundstücks Nr. 557N als Parkplatz ein Baubewilligungsverfahren durchzuführen (Ziff. 1 der Beschwerde). Neben der Gewährung der aufschiebenden Wirkung (Ziff. 2) beantragten sie in diesem Zusammenhang, C._ zu untersagen, die fragliche Parzelle Nr. 557N während der Wintersaison den Skisportlern zu Verfügung zu stellen (Ziff. 3). Das Baudepartement wies die Rechtsbegehren Ziff. 2 und 3 am 18. Dezember 2009 ab (Verfahren 09-5900). Im Rahmen des Vernehmlassungsverfahrens ergänzten die Beschwerdeführer ihre Eingabe mit dem Eventualbegehren, die Eingabe vom 9. Oktober 2009 als Rekurs entgegenzunehmen. C. Am 11. Januar 2010 wandten sich A.X._ und B.X._ erneut an die Gemeinde Nesslau-Krummenau und machten darauf aufmerksam, dass an verschiedenen Tagen wiederum zahlreiche Autos auf den Grundstücken Nrn. 540N und 557N sowie direkt am Strassenrand parkiert hätten, obwohl der offizielle Parkplatz nicht ausgelastet sei. Sie forderten deswegen, den nicht bewilligten Parkplatzbetrieb ausserhalb der Bauzone mit sofortiger Wirkung bis zum Vorliegen einer Bewilligung zu unterbinden. C._ sei zudem aufzufordern, für die von ihm angebotene Parkfläche ein Baugesuch einzureichen. Weiter verlangten sie, eine etwaige Weigerung sei in einer formellen und anfechtbaren Verfügung festzuhalten. In diesem Zusammenhang wiesen sie darauf hin, dass es sich um einen neuen Fall handle, der unabhängig vom bereits beim Baudepartement hängigen Verfahren anhand zu nehmen sei. Die Situation sei deshalb neu, weil andere und zusätzliche Parkflächen betroffen seien und weil die damalige Begründung des Gemeinderats, wonach es in der Vegetationsperiode an der Aktualität des Parkplatzproblems fehle, entfallen sei. D. Mit Beschluss vom 19. Januar 2010 nahm der Gemeinderat das Schreiben von A.X._ und B.X._ zur Kenntnis (Ziff. 1) und hielt u.a. fest, aufgrund der Sachlage werde C._ nicht aufgefordert, ein Baugesuch einzureichen (Ziff. 3). Auf den Erlass einer anfechtbaren Verfügung werde verzichtet (Ziff. 4). Dazu erwog der Gemeinderat, aufgrund der Stellungnahmen hätten weder die Sportbahn Krummenau-Wolzenalp AG noch C._ die Parkplätze für anreisende Skifahrer angeboten. Von einem Parkplatzbetrieb könne nicht die Rede sein. Das Fehlverhalten der Autofahrer sei keine baurechtliche Angelegenheit. E. Gegen diesen Beschluss rekurrierten A.X._ und B.X._ am 1. Februar 2010 ans Baudepartement; eventualiter erhoben sie wiederum Rechtsverweigerungsbeschwerde und Anzeige (Verfahren 10-819). Das Baudepartement verweigerte am 22. Februar 2010 gewisse superprovisorische Massnahmen, welche die Rekurrenten gefordert hatten. Es vereinigte die beiden Verfahren 09-5900 und 10-819 und entschied am 11. Oktober 2010 in der Sache selber. Die erste Rechtsverweigerungsbeschwerde nahm es als Rekurs entgegen und wies diesen ab. Den zweiten Rekurs hiess es teilweise gut und stellte fest, die Nutzung des Grundstücks Nr. 557N als Parkplatz für Skitouristen, so wie sie in den letzten beiden Wintersaisons betrieben worden sei, unterliege der Baubewilligungspflicht. Das Abstellen von Fahrzeugen auf dem Grundstück Nr. 540N und entlang der Kammernstrasse sei hingegen ohne Zutun von C._ erfolgt. Der Gemeinderat habe es darum bei der Feststellung bewenden lassen dürfen, das vereinzelte Falschparkieren sei kein baurechtliches Problem. F. Die Politische Gemeinde Nesslau-Krummenau und C._ erhoben gegen diesen Entscheid mit separaten Eingaben Beschwerde beim Verwaltungsgericht des Kantons St. Gallen, zogen diese aber je wieder zurück. Auch A.X._ und B.X._ gelangten ans Verwaltungsgericht. Sie beantragten insbesondere die Feststellung, dass nicht nur die Nutzung der Parzelle Nr. 557N, sondern auch diejenige sämtlicher Landwirtschaftsflächen im Gebiet Krümmenswil (Grundstücke Nrn. 540N, 555N, 566N und 547N) als Parkplatz für Skisportler der Bewilligungspflicht unterliege. Das Verwaltungsgericht wies die Beschwerde am 29. August 2011 ab. G. In ihrer Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 6. Oktober 2011 beantragen A.X._ und B.X._ die Aufhebung des verwaltungsgerichtlichen Urteils vom 29. August 2011. Eventualiter - falls auf die Beschwerde wegen Wegfalls des aktuellen Interesses (teilweise) nicht eingetreten werden sollte - seien zumindest die Disp.-Ziff. 2 und 3 des angefochtenen Entscheids aufzuheben. C._ beteiligt sich nicht am bundesgerichtlichen Verfahren. Das Baudepartement und das Verwaltungsgericht des Kantons St. Gallen schliessen je auf Abweisung der Beschwerde.