Sachverhalt:
A. An der Bürgerversammlung der politischen Gemeinde Rheineck vom 21. März 2005 lehnte die Bürgerschaft entgegen den Anträgen ihres Einbürgerungsrates zwölf in den Jahren 2003 und 2004 eingereichte Einbürgerungsgesuche ab. Aufgrund einer dagegen von einer Stimmbürgerin erhobenen Beschwerde hob das Departement des Innern des Kantons St. Gallen die ablehnenden Einbürgerungsbeschlüsse mit Entscheid vom 23. August 2005 auf. Auf Beschwerde der politischen Gemeinde Rheineck hin wies das Verwaltungsgericht des Kantons St. Gallen am 6. Dezember 2005 die Angelegenheit zur Beteiligung der Gesuchsteller am Verfahren an das Departement zurück. Dieses holte daraufhin die bis anhin unterlassene Verfahrensbeteiligung der betroffenen Gesuchsteller nach. Mit Entscheiden vom 27. April 2006 hob es die ablehnenden Einbürgerungsbeschlüsse auf und wies die politische Gemeinde Rheineck an, die Einbürgerungsgesuche der nächsten Bürgerversammlung vorzulegen, soweit die Gesuchsteller die Einbürgerungsvoraussetzungen noch erfüllten.
Die meisten Gesuchstellerinnen und Gesuchsteller hielten an ihrem Einbürgerungsgesuch fest. Sie wurden vom Einbürgerungsrat nochmals geprüft und wiederum positiv beurteilt. Dementsprechend beantragte der Einbürgerungsrat der Bürgerschaft an der Bürgerversammlung vom 19. März 2007, unter anderem den verbliebenen zehn Einbürgerungsvorlagen, welche ein zweites Mal zu beurteilen waren, zuzustimmen. Mehrere Personen nutzten an der Bürgerversammlung die Möglichkeit, die Einbürgerungen zu diskutieren. Dabei fiel die Diskussion nicht bei allen Vorlagen gleich ausführlich aus. Teilweise erfolgte überhaupt keine Wortmeldung. Die zehn Einbürgerungsgesuche wurden von der Bürgerversammlung wiederum abgelehnt.
B. Gegen die Ablehnung ihrer Einbürgerungsgesuche gelangten unter anderem A._, die Eheleute B._ (mit Sohn E._), C._ und D._ (mit den Kindern F._, G._ und H._) mit Beschwerde an das Departement des Innern mit den Anträgen:
"1. Es seien die ablehnenden Einbürgerungsbeschlüsse der Bürgerversammlung Rheineck vom 19. März 2007 aufzuheben.
2. Den Einbürgerungsgesuchen der Beschwerdeführer und Beschwerdeführerinnen sei zu entsprechen und es sei ihnen das Gemeindebürgerrecht von Rheineck zu erteilen."
Zur Begründung der Beschwerde wurde insbesondere dargelegt, die Bürgerschaft habe mit ihrem Vorgehen am 19. März 2007 klar zum Ausdruck gebracht, dass sie nicht gewillt sei, Einbürgerungsentscheide in Übereinstimmung mit der geltenden Rechtsprechung vorzunehmen. Es sei deshalb unwahrscheinlich, dass ein drittes Verfahren zu einem anderen Ergebnis führen werde. Zur Vermeidung eines prozessualen Leerlaufs sei es somit notwendig, dass das Departement in der Sache selbst entscheide.
Das Departement hiess die Beschwerden mit Entscheid vom 2. Juni 2008 teilweise gut und hob die ablehnenden Einbürgerungsbeschlüsse vom 19. März 2007 betreffend A._, die Eheleute B._ (mit Sohn E._), C._ und D._ (mit den Kindern F._, G._ und H._) auf. Es hielt fest, dass ein Teil der umstrittenen Einbürgerungsvorlagen diskussionslos abgelehnt worden sei. Eines der betroffenen Einbürgerungsgesuche sei trotz unterstützendem Votum und ein anderes gestützt auf die Religionszugehörigkeit abgewiesen worden. Eine weitere Absage sei nicht individuell begründet worden. Das Departement wies die Angelegenheit an die politische Gemeinde Rheineck zurück, damit der Einbürgerungsrat die Einbürgerungsvorlagen der Bürgerschaft an der nächsten Bürgerversammlung vorlegen könne, sofern die betroffenen Personen dannzumal die Einbürgerungsvoraussetzungen erfüllten (Dispositiv Ziff. 1 a-g des Entscheids). Soweit die Beschwerdeführer die Erteilung des Gemeinde- und Ortsbürgerrechts durch die Beschwerdeinstanz beantragt hatten, wies das Departement die Beschwerde ab (Dispositiv Ziff. 2 des Entscheids). Es wies die Gemeinde zudem darauf hin, dass bei einer erneut ungenügend begründeten Ablehnung der Vorlagen die Erteilung des Gemeinde- und Ortsbürgerrechts aufsichtsrechtlich angeordnet werden könnte (Dispositiv Ziff. 3 des Entscheids).
C. In ihrer Beschwerde an das Verwaltungsgericht des Kantons St. Gallen beantragten A._, die Eheleute B._ (mit Sohn E._), C._ und D._ (mit den Kindern F._, G._ und H._) insbesondere, Ziff. 2 des Entscheids des Departements sei aufzuheben und ihnen sei das Gemeindebürgerrecht von Rheineck zu erteilen. Eventuell sei das Departement anzuweisen, ihren Gesuchen zu entsprechen und ihnen das Bürgerrecht zu erteilen.
Mit Urteil vom 14. Oktober 2008 trat das Verwaltungsgericht auf die Beschwerde gegen Ziff. 2 des Entscheids des Departements des Innern vom 2. Juni 2008 nicht ein. Es begründete seinen Entscheid damit, dass der Verzicht auf die sofortige aufsichtsrechtliche Erteilung des Bürgerrechts nicht als Verfügung gelte, wenn die Rechtsmittelinstanz die Gesuche zur Behandlung an das gesetzlich zuständige Organ überweise. Die vorliegende Verweigerung der aufsichtsrechtlichen Erteilung des Bürgerrechts sei ein Entscheid im Rahmen der Staatsaufsicht. Dagegen sei die Beschwerde gestützt auf Art. 59bis Abs. 2 lit. a Ziff. 1 des kantonalen Verwaltungsrechtspflegegesetzes vom 16. Mai 1965 (VRP/SG; sGS 951.1) nicht zulässig, bevor die am 1. Januar 2009 ablaufende Übergangsfrist gemäss <ref-law> verstrichen sei. Erst ab diesem Datum hätten die Kantone die Rechtsweggarantie gemäss <ref-law> zu beachten und den Rechtsschutz durch ein oberes kantonales Gericht zu gewährleisten (<ref-law>).
D. Mit Verfassungsbeschwerde vom 20. November 2008 beantragen A._, die Eheleute B._ (mit Sohn E._), C._ und D._ (mit den Kindern F._, G._ und H._) im Wesentlichen, der Nichteintretensentscheid des Verwaltungsgerichts sei aufzuheben und ihnen sei das Bürgerrecht der Gemeinde Rheineck zu erteilen. Eventuell sei die Angelegenheit zur Neubeurteilung bzw. zur materiellen Entscheidung an die Vorinstanz zurückzuweisen.
Die Beschwerdeführer berufen sich auf die Menschenwürde (<ref-law>), das Diskriminierungsverbot (<ref-law>), die Begründungspflicht (<ref-law>), das Willkürverbot (<ref-law>) sowie die Bindung der staatlichen Organe an die Grundrechte (<ref-law>). Zudem machen sie Rechtsverzögerung (<ref-law>) und eine Verletzung der Art. 8 und 13 EMRK geltend. Sie bringen vor, sie hätten nach zwei verfassungswidrigen Beschlüssen der Bürgerversammlung und mehreren zu ihren Gunsten lautenden Beschwerdeentscheiden des Departements und des Verwaltungsgerichts einen Anspruch auf die Herstellung des rechtmässigen Zustands durch die Rechtsmittelinstanz. Eine nochmalige Rückweisung der Sache an die Gemeindebehörden missachte die Pflicht der Rechtsmittelinstanzen zur Rechtsgewährleistung und verfassungskonformen Beurteilung innert angemessener Frist.
E. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Mangels eines Rechtsanspruchs auf eine Einbürgerung hätten die Beschwerdeführer kein rechtlich geschütztes Interesse an der Aufhebung des angefochtenen Entscheids (<ref-law>). Eine Verletzung bundesrechtlicher Verfahrensgarantien, zu deren Rüge die Beschwerdeführer berechtigt wären (<ref-ruling> E. 2.1 S. 168), liege nicht vor.
Die Gemeinde Rheineck stellt ebenfalls den Antrag, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Sie bringt vor, es bestehe kein Anspruch auf eine Einbürgerung, sondern lediglich ein Anspruch auf Begründung des negativen Einbürgerungsentscheids. Eine Verletzung von Verfahrensrechten (fehlende Begründung) führe bloss zur Aufhebung des mangelhaften Entscheids, nicht aber zur direkten Erteilung des Bürgerrechts durch eine Rechtsmittelinstanz. Einbürgerungsorgan sei nach Art. 104 Abs. 1 KV/SG ausschliesslich die Bürgerschaft, weshalb nicht eine Rechtsmittelinstanz das Gemeindebürgerrecht reformatorisch erteilen könne.
Das kantonale Departement des Innern verzichtet auf die Einreichung einer Stellungnahme.
Die Beschwerdeführer haben von der Gelegenheit, sich zu den Stellungnahmen des Verwaltungsgerichts und der Gemeinde zu äussern, Gebrauch gemacht. Sie halten darin an ihren Anträgen und Rechtsauffassungen fest.

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten im Sinne von <ref-law> ist gemäss <ref-law> gegen Entscheide über die ordentliche Einbürgerung ausgeschlossen. Eine andere ordentliche Beschwerde fällt nicht in Betracht. Damit ist die subsidiäre Verfassungsbeschwerde gemäss <ref-law> im Grundsatz gegeben. Der Entscheid des Verwaltungsgerichts kann mit keinem kantonalen Rechtsmittel angefochten werden und ist daher kantonal letztinstanzlich (<ref-law>).
1.2 Der angefochtene Entscheid schliesst das Verfahren nicht ab. Es liegt somit kein Endentscheid im Sinne von <ref-law> vor. Mit seinem Nichteintretensentscheid hat das Verwaltungsgericht die Frage der Zuständigkeit des Departements, das Bürgerrecht anstelle der Bürgerversammlung im Rahmen des Rechtsmittelverfahrens zu erteilen, als Frage der Staatsaufsicht bezeichnet, zu deren Beurteilung es in Anwendung von Art. 59bis Abs. 2 lit. a Ziff. 1 VRP/SG nicht zuständig sei. Somit liegt in zweifacher Hinsicht ein Vor- oder Zwischenentscheid über die Zuständigkeit im Sinne von <ref-law> vor. Dieser kann mit Verfassungsbeschwerde angefochten werden, soweit dieses Rechtsmittel auch gegen den Endentscheid erhoben werden kann (Art. 92 Abs. 1 i.V.m. <ref-law>; vgl. <ref-ruling> E. 2.2 S. 647 f.). Daran ändert im vorliegenden Fall auch der Umstand nichts, dass das Verwaltungsgericht auf das bei ihm eingereichte Rechtsmittel nicht eintrat, weil es die Sache als Angelegenheit der Staatsaufsicht im Sinne von Art. 59bis Abs. 2 lit. a Ziff. 1 VRP bezeichnete.
1.3 Mit der subsidiären Verfassungsbeschwerde kann nach <ref-law> die Verletzung von verfassungsmässigen Rechten gerügt werden. Zur Beschwerde ist gemäss <ref-law> berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen (lit. a) und ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat (lit. b).
Die in <ref-law> genannte Voraussetzung ist offensichtlich erfüllt. Das nach <ref-law> erforderliche rechtlich geschützte Interesse kann durch kantonales oder eidgenössisches Gesetzesrecht oder aber unmittelbar durch ein spezielles Grundrecht oder bundesverfassungsrechtliche Verfahrensgarantien begründet sein (<ref-ruling> E. 4 S. 191 und E. 6.2 S. 199; <ref-ruling> E. 1 S. 219). Die Legitimation bei der Anrufung spezieller Verfassungsrechte ergibt sich bereits aus der Grundrechtsträgerschaft und dem Inhalt des als verletzt gerügten Verfassungsrechts (<ref-ruling> E. 2.1 S. 168). Insoweit können die Beschwerdeführer eine Verletzung der Menschenwürde (<ref-law>) und des Diskriminierungsverbots (<ref-law>) und der Bindung der staatlichen Organe an die Grundrechte (<ref-law>) geltend machen. Soweit sich die Beschwerdeführer auf eine durch ein spezielles Grundrecht geschützte Rechtsstellung berufen, kommt ihrer Rüge der Verletzung des allgemeinen Willkürverbots (<ref-law>) keine selbstständige Bedeutung zu (<ref-ruling> E. 6.2 S. 199; <ref-ruling> E. 1.3 S. 222).
Als Parteien im kantonalen Verfahren können die Beschwerdeführer zudem die Verletzung bundesverfassungsrechtlicher Verfahrensgarantien rügen, deren Missachtung eine formelle Rechtsverweigerung darstellt (<ref-ruling> E. 6.2 S. 199; <ref-ruling> E. 2.1 S. 168). Dies trifft auf die Rügen der Rechtsverzögerung (<ref-law>) und der Verletzung des Anspruchs auf rechtliches Gehör gemäss <ref-law> zu. Den Anspruch auf Begründung bei Verweigerung der Einbürgerung (vgl. <ref-ruling> E. 2 S. 58; <ref-ruling> E. 4.2 S. 147) hat der Gesetzgeber mit der am 1. Januar 2009 in Kraft getretenen Revision des Bundesgesetzes vom 29. September 1952 über Erwerb und Verlust des Schweizer Bürgerrechts (Bürgerrechtsgesetz, BüG; SR 141.0) nun auch ausdrücklich ins Bundesgesetzesrecht aufgenommen (<ref-law>; AS 2008 S. 5911).
Umstritten ist einzig, ob die Beschwerdeführer nach zwei Entscheiden der Bürgerversammlung, welche sich wegen Verletzung der Begründungspflicht als verfassungswidrig erwiesen, Anspruch auf eine umfassende verfassungskonforme Beurteilung ihrer Einbürgerungsgesuche durch eine Rechtsmittelinstanz haben. Die angerufenen speziellen Verfassungsrechte sowie die in <ref-law> verankerten Verfahrensgarantien verleihen den Beschwerdeführern als Träger dieser verfassungsmässigen Rechte im Einbürgerungsverfahren ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids. Ihre Beschwerde ist somit unter dem Gesichtspunkt der Beschwerdeberechtigung zulässig. Dies bedeutet nicht, dass die Beschwerdeführer einen Rechtsanspruch auf Einbürgerung hätten.
1.4 Nach <ref-law> sind die Beschwerdeanträge zu begründen. In der Beschwerdeschrift wird nicht begründet, weshalb Dispositiv Ziff. 4 des angefochtenen Entscheids aufzuheben sei. In dieser Ziffer des Dispositivs verzichtet das Verwaltungsgericht auf die Erhebung der auf Fr. 2'500.-- festgesetzten amtlichen Kosten. Es ist nicht ersichtlich, inwiefern die Beschwerdeführer durch diese Kostenbefreiung beschwert sind. Auf den genannten Antrag kann somit nicht eingetreten werden.
1.5 Die übrigen Sachurteilsvoraussetzungen der subsidiären Verfassungsbeschwerde sind erfüllt, so dass darauf unter Vorbehalt der Ausführungen in E. 1.4 hiervor einzutreten ist.
2. Der angefochtene Entscheid erging am 14. Oktober 2008. Die am 1. Januar 2009 in Kraft getretenen revidierten Bestimmungen des Bürgerrechtsgesetzes (AS 2008 S. 5911 f.), welche insbesondere das Verfahren in den Kantonen betreffen, sind somit auf die vorliegende Angelegenheit nicht anwendbar. Die umstrittenen verfahrensrechtlichen Fragen sind aufgrund des kantonalen Rechts und der von den Beschwerdeführern angerufenen verfassungsrechtlichen Ansprüche zu beurteilen. Die Auslegung und Anwendung des kantonalen Gesetzesrechts prüft das Bundesgericht dabei auf Willkür hin.
3. Die Beschwerdeführer machen geltend, ihre Eingabe sei zu Unrecht als Angelegenheit der Staatsaufsicht eingestuft worden, anstatt als ordentliche Beschwerde behandelt zu werden. Diese Beanstandung ist im Rahmen der Verfassungsbeschwerde gegen den verwaltungsgerichtlichen Nichteintretensentscheid zulässig (vgl. <ref-ruling> E. 1b/bb S. 406; <ref-ruling> E. 3 S. 238; je mit Hinweisen; Kölz/Häner, Verwaltungsverfahren und Verwaltungsrechtspflege des Bundes, 2. Auflage 1998, S. 168 Rz. 461; Walter Kälin, Das Verfahren der staatsrechtlichen Beschwerde, 2. Auflage 1994, S. 332).
3.1 Im Kanton St. Gallen beschliessen die Stimmberechtigten der politischen Gemeinde über die Erteilung des Gemeinde- und Ortsbürgerrechts auf Antrag des Einbürgerungsrats (Art. 104 Abs. 1 KV/SG). Besteht ein Gemeindeparlament, fasst dieses Beschluss (Art. 104 Abs. 1 Satz 2 KV/SG). Das Verfahren wird im kantonalen Gesetzesrecht geregelt (Art. 104 Abs. 3 KV/SG). Die gesetzliche Regelung über den Erwerb des Kantons- und Gemeindebürgerrechts ist im kantonalen Bürgerrechtsgesetz vom 5. Dezember 1955 (sGS 121.1) enthalten. Die Rechtsmittelordnung ergibt sich im Wesentlichen aus dem kantonalen Gemeindegesetz vom 23. August 1979 (GG; sGS 151.2) und dem kantonalen Verwaltungsrechtspflegegesetz (VRP; sGS 951.1).
Nach Art. 243 Abs. 1 GG können Stimmberechtigte und andere Personen, die an der Änderung oder Aufhebung des Beschlusses ein eigenes schutzwürdiges Interesse dartun, Beschlüsse der Bürgerschaft wegen Rechtswidrigkeit beim zuständigen Departement anfechten. Das Departement kann nach Art. 243 Abs. 3 GG auf Abstimmungsbeschwerde hin den Beschluss der Bürgerschaft aufheben (lit. a) oder angemessene Massnahmen treffen, wobei Art. 238 GG sachgemäss angewendet wird (lit. b). Gemäss Art. 238 GG trifft das zuständige Departement angemessene Massnahmen zur Wiederherstellung oder Sicherung der gesetzlichen Ordnung. Dabei kann es insbesondere anstelle eines Gemeindeorgans handeln, Ersatzvornahmen anordnen und Reglemente erlassen (Art. 238 Abs. 2 lit. a bis c GG). Der Rechtsschutz in Verwaltungsstreitsachen richtet sich nach den Vorschriften des kantonalen Verwaltungsrechtspflegegesetzes (Art. 242 GG).
3.2 Der Entscheid des Departements vom 2. Juni 2008 erging aufgrund einer Abstimmungsbeschwerde der nicht eingebürgerten Gesuchsteller in Anwendung der Art. 243 und 238 GG. Diese Bestimmungen befinden sich im Gemeindegesetz im neunten Teil betreffend die "Staatsaufsicht", welcher in die Abschnitte "I. Im Allgemeinen" (Art. 228-237 GG), "II. Zwangsmassnahmen" (Art. 238-240 GG) und "III. Rechtspflege" (Art. 241-247 GG) aufgeteilt ist. Das bedeutet bei der dargelegten Regelung des Rechtsschutzes in Gemeindeangelegenheiten nicht, dass jede Massnahme, die in sinngemässer Anwendung von Art. 238 GG ergriffen wird, eine nur beschränkt justiziable Massnahme der Staatsaufsicht darstellt. Zu unterscheiden ist, ob das Departement auf Anzeige hin entscheidet (Art. 241 GG) oder ob es im Rahmen einer Verwaltungsstreitsache tätig wird (Art. 242 GG). Die Anzeige ist nur mit beschränkten Parteirechten und -pflichten verbunden und führt in der Regel nicht zum Erlass einer anfechtbaren Verfügung (Art. 241 GG; vgl. Cavelti/Vögeli, Verwaltungsgerichtsbarkeit im Kanton St. Gallen, 2003, S. 610 f.; <ref-ruling> E. 1a S. 90). Im Beschwerdeverfahren gegen einen negativen Einbürgerungsentscheid stehen einer Partei hingegen die Verfahrensrechte des Verwaltungsrechtspflegegesetzes und der Bundesverfassung zu (vgl. Art. 242 f. GG; <ref-ruling> E. 2.1 S. 168 mit Hinweisen). Hierzu gehört im Unterschied zur aufsichtsrechtlichen Anzeige insbesondere auch der Anspruch auf einen Entscheid (Art. 63 VRP).
3.3 Der Entscheid des Departements vom 2. Juni 2008 hatte den Erlass von Verfügungen über die Einbürgerungsgesuche der Beschwerdeführer im Rahmen der Abstimmungsbeschwerde wegen Rechtswidrigkeit gemäss Art. 243 GG zum Gegenstand. In diesem Rechtsmittelverfahren entsprach das Departement den Anträgen der Beschwerdeführer teilweise, indem es die negativen Einbürgerungsentscheide wegen Rechtswidrigkeit aufhob (Dispositiv Ziffer 1a-1g des Departementsentscheids). Es lehnte jedoch den weiteren, nach Art. 243 und 238 GG im Rahmen der Abstimmungsbeschwerde grundsätzlich zulässigen Antrag der Beschwerdeführer, das Departement solle die Einbürgerungsvoraussetzungen materiell umfassend prüfen und die Einbürgerungen anstelle der Bürgerschaft vornehmen, ab (Dispositiv Ziff. 2 des Departementsentscheids). Damit bejahte das Departement entgegen dem Antrag der Beschwerdeführer die Zuständigkeit der Gemeinde zur erneuten Prüfung der Einbürgerungsvoraussetzungen. Es stellt sich die Frage, ob dieser Entscheid eine Verfügung gegenüber den Gesuchstellern darstellt, in welcher ihr Rechtsverhältnis zum Gemeinwesen geregelt wird. Das Verwaltungsgericht verneint dies, indem es ausführt, es handle sich um "keine Entscheidung im Bereich der ordentlichen gesetzlichen Zuständigkeit des Einbürgerungsrechts, sondern um die (vorläufige) Ablehnung einer Zwangsmassnahme gegenüber der Gemeinde". Die Beschwerdeführer halten dem entgegen, der Entscheid des Departements vom 2. Juni 2008 enthalte Verfügungen, d.h. auf Rechtswirkungen ausgerichtete Anordnungen, mit denen im Einzelfall Rechte und Pflichten begründet, abgeändert oder aufgehoben werden (vgl. Häfelin/Uhlmann/Müller, Allgemeines Verwaltungsrecht, 5. Auflage 2006, S. 180 ff.). Der in Dispositiv Ziff. 2 des Departementsentscheids enthaltene Entscheid über die Einbürgerung habe zweifellos Verfügungscharakter, werde doch darin der Antrag abgelehnt, die Einbürgerung sei vom Departement zu beurteilen und vorzunehmen, und damit in geschützte (Verfahrens-)Rechte der Beschwerdeführer eingegriffen.
3.4 Das Verwaltungsgericht anerkennt im angefochtenen Urteil den Verfügungscharakter des Departementsentscheids insoweit, als damit die Abstimmungsbeschwerde gutgeheissen und die Einbürgerungsgesuche zur neuen Entscheidung an die Gemeindebehörde zurückgewiesen werden (Dispositiv Ziff. 1a bis 1g des Departementsentscheids). In Bezug auf die umstrittene Dispositiv Ziff. 2 des Departementsentscheids, mit welcher der Antrag der Beschwerdeführer, das Departement solle die Einbürgerungen anstelle der Bürgerschaft vornehmen, abgewiesen wurde, verneint das Verwaltungsgericht hingegen den Verfügungscharakter. Dieser Auffassung kann nicht gefolgt werden. Zwar hat das Departement in seinem Entscheid auch ein aufsichtsrechtliches Einschreiten gegenüber der Gemeinde (zurzeit) abgelehnt. Es hat aber gleichzeitig den Antrag der Beschwerdeführer, im ordentlichen Bürgerrechtsverfahren einen reformatorischen Entscheid zu treffen, abgewiesen. Dispositiv Ziff. 2 des beim Verwaltungsgericht angefochtenen Departementsentscheids enthält somit negative Verfügungen über die Zuständigkeit zur Vornahme der beantragten Einbürgerungen. Das Departement hat an die von der Gemeinde zu vertretende Verfassungsverletzung nicht die von den Beschwerdeführern im Rechtsmittelverfahren in zulässiger Weise verlangte Rechtsfolge (Art. 238 Abs. 2 lit. a GG; Handeln anstelle des Gemeindeorgans) geknüpft. Solche auf Beschwerde im ordentlichen Einbürgerungsverfahren hin erlassene ablehnende Verfügungen des Departements sind nach Art. 59bis Abs. 1 VRP beim Verwaltungsgericht anfechtbar. Die vom Verwaltungsgericht vorgenommene Behandlung des erwähnten Rechtsbegehrens als Angelegenheit der Staatsaufsicht ist mit dem Anspruch auf gerechte Behandlung vor Gerichts- und Verwaltungsinstanzen (faires Verfahren, <ref-law>) nicht vereinbar. Die Abspaltung des im Einbürgerungsverfahren zulässigen reformatorischen Beschwerdeantrags und dessen Einstufung als Staatsaufsichtsangelegenheit stellt eine grobe Verletzung der Verfahrensrechte der Beschwerdeführer dar, verfügt doch der Beschwerdeführer im aufsichtsrechtlichen Verfahren nur über eine stark eingeschränkte Rechtsstellung (Art. 241 GG und Art. 59bis Abs. 2 lit. a Ziff. 1 VRP; E. 3.2 und Sachverhalt lit. C hiervor). Das Verwaltungsgericht hat damit seine Zuständigkeit zur Behandlung der gegen Dispositiv Ziff. 2 des Entscheids des Departements vom 2. Juni 2008 gerichteten Beschwerde in unhaltbarer Weise verneint. Die Verfassungsbeschwerde ist insoweit gutzuheissen.
4. Heisst das Bundesgericht die Beschwerde gut, so entscheidet es nach <ref-law> in der Sache selbst oder weist diese zu neuer Beurteilung an die Vorinstanz zurück. Es kann die Sache auch an die Behörde zurückweisen, die als erste Instanz entschieden hat (<ref-law>).
4.1 Die Beschwerdeführer beantragen, bei Gutheissung der Beschwerde sei ihnen das Bürgerrecht der Gemeinde Rheineck unmittelbar im bundesgerichtlichen Verfahren zu erteilen, eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Eine Erteilung des Bürgerrechts durch das Bundesgericht kann unter den vorliegenden Umständen nicht erfolgen. Die Einbürgerungsvoraussetzungen können erst aufgrund eines umfassend abgeklärten Sachverhalts materiell beurteilt werden. Die massgebenden Sachverhaltsfeststellungen sind im kantonalen Verfahren vorzunehmen. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die zuständige kantonale Instanz prüft den Sachverhalt frei und wendet das Recht von Amtes wegen an (<ref-law>). Vorliegend hat die kantonale Vorinstanz den zur materiellen Beurteilung der Einbürgerungsgesuche erheblichen Sachverhalt nicht festgestellt. Auch hat sie die Einbürgerungsvoraussetzungen unter Berücksichtigung der kantonalen Praxis nicht umfassend geprüft. Es erscheint somit gerechtfertigt, die Sache an die kantonalen Behörden zurückzuweisen (vgl. Giovanni Biaggini, Bundesgerichtsgesetz, Basler Kommentar, Rz. 16 ff. zu <ref-law>). Nach dem Grundsatz der devolutiven Wirkung der Beschwerde (sog. Devolutiveffekt) gilt im vorliegenden Verfahren auch Dispositiv Ziff. 2 des Departementsentscheids vom 2. Juni 2008 als mitangefochten (<ref-ruling> E. 1.4 S. 144 mit Hinweis). Es ist im Folgenden aufgrund der massgebenden verfassungsrechtlichen Grundsätze zu untersuchen, welche Instanz unter den gegebenen Umständen die Einbürgerungsgesuche behandeln soll.
4.2 Wer staatliche Aufgaben wahrnimmt, ist nach <ref-law> an die Grundrechte gebunden und verpflichtet, zu ihrer Verwirklichung beizutragen. Dadurch verpflichtete Grundrechtsadressaten sind zunächst die Gemeinwesen von Bund, Kantonen und Gemeinden mit allen ihren Verfassungsorganen (inkl. Stimmberechtigte; vgl. BGE <ref-ruling> E. 4 S. 146 f.; <ref-ruling> E. 3.4.2 S. 240, 217 E. 2.2.1 S. 225). Weiter richtet sich <ref-law> an die Aufsichts- und Rechtsmittelinstanzen, welche verfassungswidrige Entscheide unter gewissen Umständen nicht bloss aufzuheben, sondern den Grundrechtsschutz dadurch zu verwirklichen haben, dass sie angemessene Ersatzregelungen schaffen (Rainer J. Schweizer, Die schweizerische Bundesverfassung, St. Galler Kommentar, 2. Auflage 2008, Art. 35 Rz. 18 und 25; Bernhard Rütsche, Rechtsfolgen von Grundrechtsverletzungen, 2002, S. 350; vgl. BGE <ref-ruling> E. 4.1 S. 146; s. auch <ref-law>; <ref-ruling> E. 1.1 S. 273). Dieser Grundsatz führte im Rahmen der Praxis zur früheren staatsrechtlichen Beschwerde zu Ausnahmen von der grundsätzlich kassatorischen Natur dieses Rechtsmittels (<ref-ruling> E. 1 S. 22 mit Hinweisen; WALTER KÄLIN, a.a.O., S. 400 ff.).
4.3 Ablehnende Entscheide über Einbürgerungen unterliegen bereits vor Inkrafttreten von <ref-law> gestützt auf <ref-law> der Begründungspflicht, welche einen Teilgehalt des Anspruchs auf rechtliches Gehör darstellt (<ref-ruling> E. 3.1; <ref-ruling> E. 3 S. 20, je mit Hinweisen). Die für den Entscheid zuständigen Personen handeln, wenn sie über Einbürgerungsgesuche beschliessen, als Organ der Gemeinde und nehmen eine staatliche Aufgabe wahr. Sie sind daher gemäss <ref-law> an die Grundrechte gebunden und verpflichtet, zu ihrer Verwirklichung beizutragen (BGE <ref-ruling> E. 2.2.1 S. 225 mit Hinweisen).
4.3.1 Die Bürger von Rheineck hatten an den Versammlungen vom 21. März 2005 und 19. März 2007 Gelegenheit, ihre trotz des zustimmenden Antrags des Einbürgerungsrats ablehnende Haltung zu begründen. Zumindest an der zweiten Versammlung vom 19. März 2007 wären sie, nachdem das Departement des Innern die Sache wegen fehlender Begründung an die Gemeinde zurückgewiesen hatte und auch der Versammlungsleiter auf die Unzulässigkeit ungenügend begründeter Nichteinbürgerungen hingewiesen hatte, nach dem Anspruch der Gesuchsteller auf Gewährung des rechtlichen Gehörs (<ref-law>) verpflichtet gewesen, sämtliche Einbürgerungsvoraussetzungen umfassend zu prüfen, abschliessend zu beurteilen und die Gründe für den ablehnenden Entscheid im Einzelnen darzulegen. Dadurch wären sowohl die betroffenen Gesuchsteller als auch das Departement des Innern als Beschwerdeinstanz in die Lage versetzt worden, sich mit den dargelegten Gründen auseinanderzusetzen und diese auf ihre Stichhaltigkeit hin zu prüfen.
4.3.2 Die Bürgerversammlung hat es nach den unbestrittenen Ausführungen im Entscheid des Departements des Innern vom 2. Juni 2008 erneut versäumt, ihre Beschlüsse an der zweiten Versammlung vom 19. März 2007 in Bezug auf die Beschwerdeführer unter Beachtung der verfassungsrechtlichen Anforderungen zu fassen und zu begründen. Während die Beschlüsse der Versammlung vom März 2005 bereits wegen Missachtung des Anspruchs der Gesuchsteller auf rechtliches Gehör (<ref-law>) aufgehoben werden mussten, litten die Entscheide vom März 2007 erneut an Gehörsverletzungen und teilweise an unzulässiger Begründung der Nichteinbürgerung. Einer der beim Departement angefochtenen kommunalen Nichteinbürgerungsentscheide verstiess zudem gegen das in <ref-law> verankerte Diskriminierungsverbot. Dies führte zur Aufhebung der Nichteinbürgerungsentscheide durch das Departement, verbunden mit der Androhung, dass bei einer erneuten verfassungswidrigen Verweigerung der Einbürgerungen durch die Bürgerversammlung eine aufsichtsrechtliche Anordnung der Einbürgerung durch das Departement erfolgen könne. Das Departement ging davon aus, dass die Gemeinde bei einer dritten Behandlung der Einbürgerungsgesuche ein rechtsstaatlich korrektes Verfahren durchführen werde. Deshalb sei ihr nochmals Gelegenheit einzuräumen, einen rechtmässigen Beschluss zu fassen. Im Rahmen einer Interessenabwägung berücksichtigte das Departement die unerwünschten zeitlichen Verzögerungen. Diese seien jedoch angesichts der kantonalrechtlichen Zuständigkeit der Bürgerversammlung als Einbürgerungsorgan Ausdruck der Gemeindedemokratie und deshalb gerechtfertigt.
4.4 Diese Ausführungen sind im Lichte des verfassungsrechtlichen Anspruchs auf Beurteilung innert angemessener Frist und des Verbots der Rechtsverzögerung (<ref-law>) zu würdigen. Danach sind die Gemeinden verpflichtet, die bei ihnen hängigen Einbürgerungsverfahren ohne unnötige Verzögerungen zum Abschluss zu bringen (vgl. <ref-ruling> E. 2.2 S. 177 f., 269 E. 2.3 S. 272 f., 312 E. 5.1 S. 331, je mit Hinweisen; s. auch <ref-ruling> E. 3.4 S. 134). Die Angemessenheit einer Verfahrensdauer beurteilt sich nach der Art des Verfahrens und den konkreten Umständen einer Angelegenheit (wie Umfang und Komplexität der aufgeworfenen Sachverhalts- und Rechtsfragen, Bedeutung des Verfahrens für die Beteiligten etc.; vgl. Übersicht bei Gerold Steinmann, in: Die schweizerische Bundesverfassung, St. Galler Kommentar, 2. Auflage 2008, N. 12 zu <ref-law>). Bei der Beurteilung, ob die Dauer eines Einbürgerungsverfahrens als angemessen gelten kann, ist zu berücksichtigen, dass die eidgenössische Einbürgerungsbewilligung, die Voraussetzung für die Einbürgerung auf Kantons- und Gemeindeebene bildet, auf drei Jahre befristet ist (<ref-law>; BGE <ref-ruling> E. 4.2 S. 147). Mit dieser Befristung hat der Gesetzgeber dem Anspruch auf Beurteilung innert angemessener Frist gemäss <ref-law> entsprochen. Die in <ref-law> enthaltene Verlängerungsmöglichkeit soll nur ausnahmsweise angewendet werden, ansonsten die Befristung ihres Sinns entleert würde. Selbst wenn ein triftiger Grund für eine Fristverlängerung vorliegt, so ist von der Verlängerungsmöglichkeit im Lichte von <ref-law> zurückhaltend Gebrauch zu machen. Das Einbürgerungsverfahren darf insgesamt eine angemessene Dauer nicht überschreiten.
4.5 <ref-law> verpflichtet die Gemeinden und die Rechtsmittelinstanzen somit in verfahrensrechtlicher Hinsicht zu einer rechtskräftigen Bewältigung der Einbürgerungsverfahren innert angemessener Frist. Wie andere Grundrechte wird auch die in <ref-law> verankerte Garantie auf gleiche und gerechte Behandlung von der Forderung nach Achtung der Menschenwürde (<ref-law>) mitgetragen (Garantie des fairen Verfahrens; vgl. Müller/Schefer, Grundrechte in der Schweiz, 4. Auflage 2008, S. 821; Lorenz Engi, Was heisst Menschenwürde?, ZBl 109/2008 S. 670).
Die Einbürgerungsgesuche, die dem angefochtenen Entscheid zugrunde liegen, wurden in den Jahren 2003 und 2004 eingereicht. Seither haben die Beschwerdeführer das kommunale Einbürgerungsverfahren mit anschliessendem kantonalem Rechtsmittelverfahren bereits zweimal durchlaufen. Die Gesuche wurden vom zuständigen kommunalen Einbürgerungsrat beide Male positiv beurteilt, dann aber von der Bürgerversammlung ohne verfassungskonforme Begründung abgelehnt. Das Departement des Innern hat mit der wiederholten Rückweisung der Sache an die Gemeinde verkannt, dass eine solche Rückweisung zu neuer Entscheidung sinnvoll sein kann, wenn eine Verwaltungsbehörde angesprochen wird, während das gleiche Verfahren eine selbstbewusste Versammlung schweizerischer Stimmberechtigter nur zum Widerstand provoziert. In solchen Fällen soll das Departement als für Bürgerrechtsfragen zuständige Instanz auf Beschwerde hin anstelle der Gemeinde direkt in der Sache entscheiden und auf eine Rückweisung verzichten. Dies entspricht offenbar auch seiner Absicht in zukünftigen Fällen (Yvo Hangartner, Grundsatzfragen der Einbürgerung nach Ermessen, ZBl 110/2009 S. 311). Das Departement wird eine allfällige Veränderung der individuellen Verhältnisse in Bezug auf die Einbürgerungsvoraussetzungen unter Wahrung des Anspruchs auf rechtliches Gehör der betroffenen Personen und der Gemeinde prüfen müssen, bevor es über die Einbürgerungen entscheidet. In diesem Sinne ist die Sache in Anwendung von Art. 107 Abs. 2 in Verbindung mit <ref-law> an das Departement des Innern zur neuen Beurteilung zurückzuweisen.
5. Zusammenfassend ergibt sich, dass die Beschwerde teilweise gutzuheissen und die Ziff. 1 und 5 des Urteils des Verwaltungsgerichts vom 14. Oktober 2008 sowie Ziff. 2 des Entscheids des Departement des Innern vom 2. Juni 2008 aufzuheben sind. Die Sache wird an das Departement des Innern zu neuer Beurteilung zurückgewiesen.
Der unterliegenden Gemeinde Rheineck sind keine Gerichtskosten aufzuerlegen (<ref-law>). Sie hat die Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>). Für das verwaltungsgerichtliche Verfahren hat die politische Gemeinde Rheineck den Beschwerdeführern überdies eine angemessene Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und Ziff. 1 und 5 des Urteils des Verwaltungsgerichts des Kantons St. Gallen vom 14. Oktober 2008 sowie Ziff. 2 des Entscheids des Departements des Innern des Kantons St. Gallen vom 2. Juni 2008 werden aufgehoben. Die Sache wird an das Departement des Innern zu neuer Beurteilung zurückgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Die politische Gemeinde Rheineck hat den Beschwerdeführern für das bundesgerichtliche Verfahren eine Parteientschädigung von insgesamt Fr. 3'000.-- und für das verwaltungsgerichtliche Verfahren eine Parteientschädigung von insgesamt Fr. 2'000.-- zu bezahlen.
4. Dieses Urteil wird den Beschwerdeführern, der Politischen Gemeinde Rheineck sowie dem Departement des Innern und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 7. Juli 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Haag