Sachverhalt:
A. Der Gemeinderat Walenstadt bewilligte der politischen Gemeinde Walenstadt am 2. September 2004 die Errichtung eines Kinderspielplatzes auf dem Grundstück Nr. 912 und eines asphaltierten Hartplatzes auf dem angrenzenden Grundstück Nr. 930. Diese Grundstücke liegen neben einem ehemaligen Schulhaus in der Zone für öffentliche Bauten und Anlagen.
Mit Eingabe vom 14. Juni 2006 gelangten unter anderem die Ehegatten X._, Eigentümer des unmittelbar an den Hartplatz angrenzenden, in der Wohnzone W2 gelegenen Grundstücks Nr. 926, an das Bausekretariat Walenstadt. Sie beanstandeten, dass die Nutzung des Hartplatzes und des Kinderspielplatzes ohne Bewilligung erweitert werde. Sie beantragten insbesondere die Durchführung eines Baubewilligungsverfahrens für unbewilligte Änderungen sowie vorsorgliche Massnahmen (Baueinstellungsverfügung und Nutzungsverbot) und die Entfernung von rechtswidrigen Anlageteilen. Nach Durchführung eines Augenscheins teilte der Gemeinderat Walenstadt den Ehegatten X._ mit, für das Spielfeld sei weder ein nachträgliches Baubewilligungsverfahren noch ein Nutzungsverbot nötig. Nach weiterer Korrespondenz zwischen der Gemeinde und den betroffenen Nachbarn ersuchten diese am 2. November 2006 den Gemeinderat Walenstadt, bis zum 15. November 2006 eine anfechtbare Verfügung zu erlassen. Nachdem die Gemeinde diesem Gesuch nicht nachkam, erhoben unter anderem die Ehegatten X._ beim Baudepartement des Kantons St. Gallen eine Rechtsverweigerungsbeschwerde. Sie beantragten, die Gemeinde sei anzuhalten, über die am 14. Juni 2006 beantragten vorsorglichen Massnahmen zu entscheiden. Weiter verlangten sie die Durchführung eines nachträglichen Baubewilligungsverfahrens für die Umnutzung-/Nutzungserweiterung des Hartplatzes und für die in Abweichung von der Baubewilligung vom 2. September 2004 erstellten Anlageteile und Geländeveränderungen. Mit Schreiben vom 20. Juni 2007 rügten die Beschwerdeführer beim Gemeinderat Walenstadt, dass auf dem Hartplatz ohne Bewilligung Basketballkörbe aufgestellt würden. Sie beantragten die umgehende Einstellung der Bauarbeiten. Diese Beanstandung beantwortete der Gemeinderat Walenstadt mit Hinweis auf die rechtskräftige Bewilligung des Spielplatzes, worauf die Ehegatten X._ am 27. Juni 2007 beim Baudepartement eine aufsichtsrechtliche Anzeige gegen den Gemeinderat Walenstadt einreichten.
Mit Entschied vom 17. März 2008 trat das Baudepartement auf die Rechtsverweigerungsbeschwerde nicht ein und gab der aufsichtsrechtlichen Anzeige gegen den Gemeinderat Walenstadt keine Folge. Dagegen erhoben unter anderem die Ehegatten X._ Rekurs bei der Regierung des Kantons St. Gallen. Diese gab der aufsichtsrechtlichen Anzeige mit Beschluss vom 21. Oktober 2008 ebenfalls keine Folge und wies den Rekurs im gleichen Beschluss ab, soweit sie darauf eintrat.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 24. November 2008 beantragen die Ehegatten X._, der Entscheid der Regierung vom 21. Oktober 2008 sei aufzuheben, ihr Rekurs an die Regierung sei in Bezug auf die nachträglich errichteten Handballtore und Basketballkörbe gutzuheissen und die Gemeinde Walenstadt sei zu verpflichten, das ordentliche Baubewilligungsverfahren einzuleiten. Sie rügen insbesondere, es sei zu Unrecht kein Baubewilligungsverfahren für die umstrittenen Änderungen des Spielplatzes durchgeführt worden.
C. Der Gemeinderat Walenstadt verzichtet auf eine Stellungnahme zur Beschwerde. Das Departement des Innern des Kantons St. Gallen beantragt, die Beschwerde abzuweisen.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob und inwieweit auf ein Rechtsmittel eingetreten werden kann (Art. 29 Abs. 1 BGG; <ref-ruling> E. 1.1 S. 251).
1.1 Angefochten ist ein kantonaler Endentscheid über die Baubewilligungspflicht für eine Handball- und Basketballanlage auf einem Spielplatz. Es handelt sich dabei um eine öffentlich-rechtliche Angelegenheit im Sinne von Art. 82 lit. a BGG, welche grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten unterliegt (<ref-ruling> E. 1.2 S. 251). Die aufsichtsrechtliche Anzeige ist nicht Streitgegenstand des bundesgerichtlichen Verfahrens.
1.2 Die Beschwerde ist nach Art. 86 Abs. 1 lit. d BGG zulässig gegen Entscheide letzter kantonaler Instanzen, sofern nicht die Beschwerde an das Bundesverwaltungsgericht zulässig ist. Die Kantone setzen als unmittelbare Vorinstanzen des Bundesgerichts obere Gerichte ein, soweit nicht nach einem anderen Bundesgesetz Entscheide anderer richterlicher Behörden der Beschwerde an das Bundesgericht unterliegen (Art. 86 Abs. 2 BGG). Für Entscheide mit vorwiegend politischem Charakter können die Kantone anstelle eines Gerichts eine andere Behörde als unmittelbare Vorinstanz des Bundesgerichts einsetzen (Art. 86 Abs. 3 BGG). Nach Art. 130 Abs. 3 BGG erlassen die Kantone innert zwei Jahren nach Inkrafttreten des Bundesgerichtsgesetzes unter anderem Ausführungsbestimmungen über die Zuständigkeit, die Organisation und das Verfahren der Vorinstanzen im Sinne von Art. 86 Abs. 2 und 3 BGG. Bis zum Erlass der Ausführungsgesetzgebung können die Kantone die Ausführungsbestimmungen nötigenfalls und vorläufig in die Form nicht referendumspflichtiger Erlasse kleiden (Art. 130 Abs. 4 BGG).
1.2.1 Anfechtungsobjekt bildet ein Entscheid der kantonalen Regierung, welcher nicht an das Bundesverwaltungsgericht weitergezogen werden kann. Da es sich bei der Regierung nicht um eine richterliche Behörde handelt, ist die nach Art. 86 Abs. 2 zweiter Halbsatz BGG zulässige Ausnahme nicht zu prüfen. Auch liegt offensichtlich kein Entscheid mit vorwiegend politischem Charakter im Sinne von Art. 86 Abs. 3 BGG vor.
1.2.2 Das Bundesgerichtsgesetz ist am 1. Januar 2007 in Kraft getreten (vgl. AS 2006 1069). Die Frist nach Art. 130 Abs. 3 BGG lief damit am 31. Dezember 2008 ab. Der angefochtene Beschluss wurde am 21. Oktober 2008 gefällt, weshalb sich die Frage stellt, ob gestützt auf Art. 130 Abs. 3 BGG gegen den Beschluss der Regierung die Beschwerde an das Bundesgericht zulässig ist, obwohl es sich bei dieser Vorinstanz nicht um ein oberes Gericht im Sinne von Art. 86 Abs. 2 BGG handelt.
1.2.3 Die Beschwerdeführer berufen sich auf das Umweltrecht des Bundes und beklagen sich insbesondere über die mit der Veränderung der umstrittenen Anlage verbundenen Lärmimmissionen. Sie machen sinngemäss geltend, mit der unterbliebenen Beurteilung der Zulässigkeit der Handballtore und Basketballkörbe in einem ordentlichen Baubewilligungsverfahren sei auch eine Anwendung des Umweltrechts verunmöglicht worden.
Die Auslegung und Anwendung des Umweltschutzrechts des Bundes bei unerwünschten Lärmimmissionen von Kinderspielplätzen und Sportanlagen war vor Inkrafttreten des Bundesgerichtsgesetzes im Rahmen der Verwaltungsgerichtsbeschwerde an das Bundesgericht (Art. 97 ff. OG) zu beurteilen (<ref-ruling>; <ref-ruling>; <ref-ruling>). Bereits gestützt auf Art. 98a OG hatten die Kantone richterliche Behörden als letzte kantonale Instanzen zu bestellen, soweit gegen deren Entscheide unmittelbar die Verwaltungsgerichtsbeschwerde an das Bundesgericht zulässig war. Diese Regelung wird mit Art. 86 Abs. 2 BGG im Wesentlichen weitergeführt. Mit der Übergangsregelung von Art. 130 Abs. 3 BGG wurde keine neue Übergangsfrist geschaffen für Fälle, in welchen bereits nach Art. 98a OG ein letztes kantonales Gericht zur Verfügung stehen musste (vgl. <ref-ruling> E. 3.5 S. 136; zur Publikation bestimmtes Urteil des Bundesgerichts 6B_573/2008 vom 22. Dezember 2008 E. 2.4; Botschaft zur Totalrevision der Bundesrechtspflege, BBl 2001 4227 f. und 4354; Denise Brühl-Moser, Bundesgerichtsgesetz, Basler Kommentar, Rz. 16 zu Art. 130 BGG). Art. 86 Abs. 2 BGG verlangt lediglich zusätzlich zu Art. 98a Abs. 1 OG, dass es sich bei der kantonalen Gerichtsinstanz um ein oberes Gericht handeln muss (zum Begriff des oberen Gerichts vgl. Urteil des Bundesgerichts 2C_25/2009 vom 5. Februar 2009 E. 4).
1.2.4 Nach der kantonalen Verfahrensordnung besteht gegen Entscheide der Regierung über Rechtsverweigerungsbeschwerden kein Rechtsmittel an das Verwaltungsgericht des Kantons St. Gallen, da die Regierung als Beschwerdeinstanz endgültig entscheidet (Art. 89 des kantonalen Gesetzes über die Verwaltungsrechtspflege vom 16. Mai 1965). Diese Rechtsmittelordnung ist in Bezug auf Entscheide, die sich auf Bundesverwaltungsrecht stützen oder hätten stützen sollen, nicht mit der bisherigen Regelung gemäss Art. 98a Abs. 1 OG vereinbar. Der Umstand, dass das kantonale Recht offenbar nicht an diese seit dem 15. Februar 1992 bestehende Bestimmung angepasst wurde, kann nach den Erwägungen in E. 1.2.3 hiervor nicht dazu führen, dass nach dem Inkrafttreten des Bundesgerichtsgesetzes während der Übergangsfrist von Art. 130 Abs. 3 BGG auf die Beurteilung durch ein kantonales Gericht im Sinne der früheren Regelung verzichtet wird. Vielmehr ist auf die vorliegende Beschwerde mangels Letztinstanzlichkeit des angefochtenen Entscheids gemäss Art. 86 Abs. 2 BGG nicht einzutreten. Die Sache ist an das kantonale Verwaltungsgericht, das für bau- und umweltrechtliche Streitigkeiten zuständig ist (Urteil des Bundesgerichts 1C_397/2007 vom 27. Mai 2008), zur Behandlung der Beschwerde zu überweisen (vgl. <ref-ruling> E. 1.3.2 S. 203 mit Hinweisen; zur Publikation bestimmtes Urteil des Bundesgerichts 2C_25/2009 vom 5. Februar 2009 E. 6.2).
2. Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 4 BGG). Der Kanton St. Gallen hat den Beschwerdeführern jedoch eine angemessene Parteientschädigung auszurichten (Art. 68 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Die Sache wird dem Verwaltungsgericht des Kantons St. Gallen zur Behandlung der Beschwerde überwiesen.
3. Es werden keine Gerichtskosten erhoben.
4. Der Kanton St. Gallen hat den Beschwerdeführern eine Parteientschädigung von Fr. 2'000.-- zu bezahlen.
5. Dieses Urteil wird den Beschwerdeführern, dem Gemeinderat Walenstadt und der Ortsgemeinde Tscherlach sowie der Regierung und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 26. März 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Haag