Sachverhalt:
A.
A.a. Der Kanton Appenzell Ausserrhoden und die Appenzeller Bahnen planen in der Gemeinde Teufen/AR ein Projekt zur Ortsdurchfahrt durch die Bahn (sog. Projekt Doppelspur). Der von Rolf Brunner und Philipp Schuchter präsidierte Verein "Interessengemeinschaft Tüüfner Engpass" (nachfolgend: Interessengemeinschaft) mit Sitz in Teufen verfolgt den primären Zweck, im Interesse der Gemeinde Teufen sowie den angrenzenden Gemeinden einen für die Gemeinde und das Appenzellerland intakten und lebensfähigen Dorfkern zu realisieren. Am 20. Dezember 2019 reichte die Interessengemeinschaft eine Volksinitiative mit folgendem Wortlaut ein:
" Der Gemeinderat wird ersucht, über die Variante Doppelspur durch den Dorfkern abstimmen zu lassen. Den Stimmbürgern sind dabei die Gesamtkosten und die Aufteilung zwischen Bahn/Bund, Kanton und Gemeinde aufzuzeigen."
Am 14. Januar 2020 stellte der Gemeinderat Teufen fest, dass die Initiative mit 799 gültigen Unterschriften zustande gekommen sei.
A.b. In der Folge befasste sich der Gemeinderat mit der Frage der Gültigkeit der Initiative und holte dazu ein Gutachten ein, das auf Ungültigkeit lautete, weil das strittige Projekt (Doppelspur) nur sehr eingeschränkt in der Kompetenz der Gemeinde liege. Die Interessengemeinschaft legte dazu eine eigene Expertise mit davon abweichender Einschätzung vor. Daraufhin kam es zu einem Gedankenaustausch zwischen der Gemeinde und der Interessengemeinschaft, wobei auch über eine Kompromisslösung nachgedacht wurde. Am 27. Februar 2020 fand dazu eine ausserordentliche Gemeinderatssitzung statt, an der eine Delegation der Interessengemeinschaft teilnahm. In einem daran anschliessenden Schreiben an die Interessengemeinschaft teilte der Gemeinderat mit, über die Gültigkeit der Initiative zu entscheiden, falls diese bis zum 16. März nicht zurückgezogen werde. Mit Nachrichten vom 19. und 25. März 2020 lehnte das Initiativkomitee einen bedingungslosen Rückzug der Initiative ab.
A.c. Am 26. März 2020 veröffentlichte der Gemeinderat Teufen eine Medienmitteilung, wonach er die Initiative der Interessengemeinschaft für ungültig erklärt habe. Diese Medienmitteilung wurde der Interessengemeinschaft am gleichen Tag vorab per Mail zugestellt, worauf die Interessengemeinschaft ebenfalls gleichentags eine eigene Medienmitteilung publizierte.
Erneut noch am selben 26. März 2020 ersuchte die Interessengemeinschaft den Gemeinderat, ihr den Entscheid über die Ungültigerklärung formell zu eröffnen. Mit Schreiben vom 30. März 2020, das bereits vorab noch am gleichen Tag per Mail zugestellt wurde, teilte der Gemeinderat mit, seiner Bekanntgabepflicht nachgekommen zu sein; eine weitere Information finde nicht statt.
A.d. Am 2. April 2020 erhoben die Interessengemeinschaft sowie ihre beiden Präsidenten Rolf Brunner und Philipp Schuchter Beschwerde beim Regierungsrat des Kantons Appenzell Ausserrhoden mit dem Hauptantrag, den Entscheid des Gemeinderats Teufen über die Ungültigkeit der Volksinitiative für eine Abstimmung über die Doppelspur der Ortsdurchfahrt aufzuheben. Mit Beschluss vom 25. August 2020 trat der Regierungsrat darauf mangels rechtzeitiger Erhebung der Beschwerde nicht ein.
B.
Am 15. Februar 2021 wies das Obergericht Appenzell Ausserrhoden eine dagegen von der Interessengemeinschaft sowie Rolf Brunner und Philipp Schuchter eingereichte Beschwerde ab, soweit es darauf eintrat.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten als Stimmrechtsbeschwerde an das Bundesgericht beantragen die Interessengemeinschaft sowie Rolf Brunner und Philipp Schuchter, das Urteil des Obergerichts aufzuheben und die Streitsache zur Neubeurteilung an eine der Vorinstanzen zurückzuweisen; eventuell sei die Volksinitiative für gültig zu erklären. Zur Begründung wird im Wesentlichen geltend gemacht, der Entscheid des Gemeinderats hätte den Initianten formell eröffnet werden müssen. So oder so habe die einschlägige dreitägige Beschwerdefrist frühestens am 30. März 2020 zu laufen begonnen, weshalb die Beschwerde am 2. April 2020 rechtzeitig eingereicht worden sei.
Der Gemeinderat Teufen reichte innert Frist keine Stellungnahme ein. Das Departement Inneres und Sicherheit des Kantons Appenzell Ausserrhoden schliesst im Auftrag des Regierungsrats auf Abweisung der Beschwerde. Das Obergericht stellt Antrag auf Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1.
1.1. Angefochten ist das Urteil des Obergerichts Appenzell Ausserrhoden vom 15. Februar 2021, das den Nichteintretensentscheid des Regierungsrats Appenzell Ausserrhoden bestätigt. Inhaltlich rügten die Beschwerdeführer vor dem Regierungsrat, die vom Gemeinderat Teufen ausgesprochene Ungültigerklärung verletze ihre politischen Rechte. Gegen den angefochtenen kantonal letztinstanzlichen Endentscheid steht grundsätzlich die Beschwerde in Stimmrechtssachen gemäss Art. 82 lit. c und Art. 88 BGG offen.
1.2. Die Beschwerdeführer 2 und 3 sind unbestrittenermassen in Teufen stimmberechtigt und daher zur Beschwerde legitimiert (<ref-law>). Auch die als Verein und damit als juristische Person organisierte Beschwerdeführerin 1 (Interessengemeinschaft Tüüfner Engpass), deren Zweck in engem Konnex zur Streitfrage steht, ist nach der Praxis zu <ref-law> zur Beschwerde in Stimmrechtssachen berechtigt (vgl. <ref-ruling> E. 2.2.4; <ref-ruling> E. 1.3.1; mit Hinweisen).
1.3. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
1.4. Im Rahmen der Beschwerde in Stimmrechtssachen prüft das Bundesgericht nicht nur die Auslegung von Bundesrecht und von kantonalem Verfassungsrecht frei, sondern auch diejenige anderer kantonaler Vorschriften, die den Inhalt des Stimm- und Wahlrechts normieren oder mit diesem in engem Zusammenhang stehen (<ref-law>; <ref-ruling> E. 3.1 mit Hinweis).
2.
Verfahrensgegenstand vor dem Obergericht bildete die Frage, ob die Frist für die Beschwerde an den Regierungsrat eingehalten sei. Da sich der Streitgegenstand im Rechtsschutzverfahren nach oben nur einschränken, aber nicht erweitern kann, beschränkt er sich auch vor Bundesgericht auf diese Frage. Der von den Beschwerdeführern gestellte materielle Eventualantrag, die Volksinitiative für gültig zu erklären, erweist sich damit von vornherein als unzulässig. Insoweit kann auf die Beschwerde daher nicht eingetreten werden.
3.
3.1. Nach <ref-law> sind die politischen Rechte gewährleistet (Abs. 1); die Garantie der politischen Rechte schützt die freie Willensbildung und die unverfälschte Stimmabgabe (Abs. 2). <ref-law> garantiert die politischen Rechte auf Bundes- sowie Kantons- und Gemeindeebene in abstrakter Weise und ordnet die wesentlichen Grundzüge der demokratischen Partizipation im Allgemeinen. Der Gewährleistung kommt Grundsatzcharakter zu. Sie weist Bezüge zur Rechtsgleichheit (<ref-law>) sowie zur Rechtsweggarantie (<ref-law>) auf. Der konkrete Gehalt der politischen Rechte mit ihren mannigfachen Teilgehalten ergibt sich nicht aus der Bundesverfassung, sondern in erster Linie aus dem spezifischen Organisationsrecht des Bundes bzw. der Kantone und allenfalls der Gemeinden (<ref-ruling> E. 4.3 S. 266 f.; <ref-ruling> E. 3.3; je mit Hinweis).
3.2. Gemäss gefestigter bundesgerichtlicher Rechtsprechung ist eine im kantonalen Recht festgelegte dreitägige Frist für die Erhebung der Stimmrechtsbeschwerde für sich allein nicht verfassungswidrig. Das Bundesgericht hielt allerdings fest, eine Frist von drei Tagen sei sehr kurz und lasse dem Stimmberechtigten wenig Zeit, die Sach- und Rechtslage abzuklären und eventuell anwaltlichen Rat einzuholen, um die Erfolgsaussichten einer Beschwerde abzuwägen. Es stellte daher auch darauf ab, unter welchen Umständen diese kurze Frist gelten soll. So wird zunächst die Erforderlichkeit sofortigen Handelns vorausgesetzt, was gemäss der Rechtsprechung in Stimmrechtssachen allerdings regelmässig zutrifft. Die kurze Frist bezweckt insbesondere, dass Mängel möglichst noch vor der Wahl oder Abstimmung behoben werden können und der Urnengang nicht wiederholt zu werden braucht. Auch soll ein Schwebezustand im Volksinitiativverfahren vermieden werden (vgl. (<ref-ruling> E. 3; <ref-ruling> E. 4.4; <ref-ruling> E. 3b; Urteile des Bundesgerichts 1C_555/2019 vom 9. September 2020 E. 4.5 und 1C_577/2013 vom 2. Oktober 2013 E. 3.1, in: ZBl 115/2014 S. 512). Die Anwendung der kurzen Frist darf jedoch den Stimmberechtigten im konkreten Fall eine Beschwerdeerhebung nicht praktisch verunmöglichen. Namentlich wird vorausgesetzt, dass die zeitgerechte Erkennbarkeit von Verfahrensmängeln oder Unregelmässigkeiten sichergestellt ist. Ebenso ist an die Beschwerdebegründung kein strenger Massstab anzulegen (Urteile des Bundesgerichts 1C_555/2019 vom 9. September 2020 E. 4.5 und 1C_62/2012 vom 18. April 2012 E. 3; je mit Hinweis auf BGE <ref-ruling> E. 3b sowie weitere Urteile).
3.3. Nach Art. 1 Abs. 1 des Gesetzes vom 9. September 2002 über die Verwaltungsrechtspflege des Kantons Appenzell Ausserrhoden (VRPG; bGS 143.1) gelten die Bestimmungen des Verwaltungsrechtspflegegesetzes nur insoweit, als nicht besondere Vorschriften bestehen. Solche finden sich im kantonalen Gesetz vom 24. April 1988 über die politischen Rechte (GPR; bGS 131.12). Nach Art. 38 GPR sind die Ergebnisse von Wahlen und Abstimmungen so rasch wie möglich durch Anschlag zu veröffentlichen, wobei die Publikation einen Hinweis auf die Beschwerdefrist und die Beschwerdeinstanz zu enthalten hat. Art. 49 ff. GPR regeln die Volksinitiative in Kanton und Gemeinde. Gemäss Art. 57 Abs. 2 GPR entscheidet der Gemeinderat oder in Gemeinden mit Gemeindeparlament dieses letztere über die Gültigkeit einer kommunalen Initiative. Nach Art. 62 GPR kann wegen Verletzung des Stimmrechts sowie wegen Unregelmässigkeiten bei der Vorbereitung und Durchführung von Wahlen und Abstimmungen beim Regierungsrat Beschwerde geführt werden (Abs. 1); die Beschwerde ist innert drei Tagen seit der Entdeckung des Beschwerdegrundes, spätestens jedoch am dritten Tag nach der amtlichen Veröffentlichung der Ergebnisse einzureichen (Abs. 2). Beschwerdeentscheide des Regierungsrats können innert 30 Tagen mit Beschwerde an das Obergericht weitergezogen werden (Art. 65bis GRP), wie das hier geschehen ist.
3.4. Die Gemeindeordnung der Gemeinde Teufen vom 22. September 2002 (GO) regelt das kommunale Initiativrecht in Art. 9 ff. Nach Art. 11 GO entscheidet der Gemeinderat unter anderem über die Gültigkeit einer Initiative. Gemäss Art. 19 lit. q GO bezeichnet er auch die amtlichen Publikationsorgane. Im Webauftritt der Gemeinde Teufen auf dem Internet werden folgende Publikationsorgane als amtliche dieser Gemeinde geführt: als lokales Publikationsorgan "Tüüfner Poscht" sowie als amtliche Publikationsorgane "Amtsblatt vom Kanton Appenzell Ausserrhoden" und "Appenzeller Tagblatt" (besucht am 1. Oktober 2021).
3.5. In tatsächlicher Hinsicht ergibt sich aus dem angefochtenen Entscheid in wesentlicher Übereinstimmung mit den Akten, dass der Gemeinderat Teufen am 26. März 2020 eine Medienmitteilung veröffentlichte, wonach er die sog. "Volksinitiative Doppelspur" der Interessengemeinschaft (Beschwerdeführerin 1) für ungültig erklärt habe. Die Medienmitteilung wurde der Interessengemeinschaft am gleichen Tag vorab per Mail zugestellt, worauf die Beschwerdeführerin 1 ebenfalls gleichentags eine eigene Medienmitteilung publizierte. Am 27. März 2020 erschien in der Appenzeller Zeitung ein auf der Medienmitteilung des Gemeinderats Teufen beruhender Artikel über die Ungültigerklärung der "Doppelspur-Initiative". Mit vorab per Mail am 30. März 2020 zugestelltem Schreiben vom gleichen Tag teilte der Gemeinderat der Beschwerdeführerin 1 mit, seiner Bekanntgabepflicht nachgekommen zu sein; eine weitere Information gemäss einem Gesuch der Interessengemeinschaft vom 26. März 2020 um formelle Eröffnung des Entscheids über die Ungültigerklärung finde nicht statt. Am 2. April 2020 erhoben die Beschwerdeführer Beschwerde beim Regierungsrat. Dieser beurteilte die gesetzliche Dreitagesfrist als verpasst, was das Obergericht auf Beschwerde hin bestätigte. Die Beschwerdeführer rügen zwar auch, der Sachverhalt sei vom Obergericht offensichtlich unrichtig erhoben worden. Das ist aber im Hinblick auf die massgeblichen Sachverhaltselemente nicht nachvollziehbar, womit sich die diesbezüglichen tatsächlichen Feststellungen im angefochtenen Urteil für das Bundesgericht als verbindlich erweisen.
4.
4.1. Die Beschwerdeführer rügen zunächst, der Entscheid des Gemeinderats über die Ungültigerklärung hätte ihnen formell eröffnet werden müssen. Sie stützen sich dafür auf ihren Anspruch auf rechtliches Gehör gemäss <ref-law> sowie Art. 20 Abs. 4 der Verfassung des Kantons Appenzell Ausserrhoden vom 30. April 1995 (SR 131.224.1), auf die Rechtsweggarantie gemäss <ref-law> sowie auf das Willkürverbot nach <ref-law>. Sie hätten dem Gemeinderat im Übrigen auch ein entsprechendes Gesuch unterbreitet, dem dieser aber nicht stattgegeben habe. Ohne formelle Zustellung des Entscheids habe die Beschwerdefrist gar nicht zu laufen begonnen. Ergänzend berufen sich die Beschwerdeführer auf den Grundsatz von Treu und Glauben gemäss <ref-law>.
4.2. Nach Art. 62 Abs. 2 GPR ist die Beschwerde innert drei Tagen seit der Entdeckung des Beschwerdegrundes, spätestens jedoch am dritten Tage nach der amtlichen Veröffentlichung der Ergebnisse einzureichen. Mit dem Wort "Ergebnisse" sind in erster Linie solche von Wahlen und Abstimmungen gemeint, wie sich unschwer aus dem Sachzusammenhang der Bestimmung ergibt. Die Ungültigerklärung ist kein Ergebnis im Sinne von Art. 62 Abs. 2 GPR. Die Frist kann aber zwangsläufig erst zu laufen beginnen, wenn die Ungültigerklärung entdeckt, d.h. bekannt wird, oder, in Analogie zur Publikation von Ergebnissen von Wahlen und Abstimmungen, wenn sie amtlich veröffentlicht wird. Die Beschwerdeführer behaupten, ihnen als Initianten hätte der Entscheid über die Ungültigerklärung zwingend formell eröffnet werden müssen, womit die Beschwerdefrist erst zu laufen begonnen hätte.
4.3. Das Obergericht behandelte den strittigen Entscheid über die Ungültigerklärung der fraglichen Initiative wie einen Realakt und erachtete deswegen eine formelle Eröffnung als nicht erforderlich. Mit der Vorinstanz ist davon auszugehen, dass sich eine Beschwerde in Stimmrechtssachen nicht nur gegen eigentliche Verfügungen richten kann, sondern gegen alle staatlichen Akte, welche die politischen Rechte nach <ref-law> betreffen. Zu den nach Art. 62 GPR anfechtbaren behördlichen Akten können daher Handlungen unterschiedlicher Natur, worunter Realakte, zählen. Im Schrifttum wird der Entscheid über die Ungültigkeit einer Initiative allerdings nicht als Realakt, sondern als rechtlicher Akt, typischerweise als Feststellungs- und Allgemeinverfügungsentscheid, beurteilt (vgl. CORSIN BISAZ, Direktdemokratische Instrumente als "Anträge aus dem Volk an das Volk", 2020, Rz. 618 und 620, mit weiteren Literaturhinweisen). Gemäss der bundesgerichtlichen Rechtsprechung handelt es sich beim Entscheid über die Gültigkeit einer Volksinitiative jedenfalls nicht um einen Legislativakt. Ergeht der Entscheid vor der Unterschriftensammlung, kann, insbesondere bei Exekutiventscheiden, allenfalls von einem individuell-konkreten Hoheitsakt ausgegangen werden, der sich an die Initianten richtet, denen gewisse Parteirechte wie etwa ein Anhörungsrecht zustehen müssen (so auch BISAZ, a.a.O., Rz. 620). Wurde jedoch mit der Unterschriftensammlung begonnen oder ist diese bereits abgeschlossen, stehen die Initianten nicht mehr allein hinter der Initiative. Allen, welche die Initiative mittragen, die Parteirechte zu gewähren, ist nur schon aus praktischen Gründen ausgeschlossen. Verfahrensrechte wie namentlich der Anspruch auf rechtliches Gehör kommen diesfalls höchstens aufgrund besonderer Umstände in Frage (vgl. <ref-ruling> E. 4.3 und 4.4).
4.4. Nochmals komplexer stellt sich die Frage eines allfälligen Anspruchs auf formelle Eröffnung des Ungültigkeitsbefunds dar. Das hier einschlägige kantonale Recht schreibt nicht vor, dass ein entsprechender Entscheid den Initianten förmlich zuzustellen sei. Soweit ersichtlich, wird solches auch im Schrifttum nicht gefordert. Im Übrigen würde sich insofern zudem die Frage stellen, ob eine Eröffnung nicht für alle Stimmberechtigten gleichermassen erforderlich wäre. Andererseits darf keine stimmberechtigte Person durch den Verzicht auf formelle Eröffnung einen Rechtsnachteil, insbesondere im Hinblick auf allfällige prozessuale Rechte, erleiden, solange sie vom entsprechenden Entscheid und von dessen zumindest minimaler Begründung keine Kenntnis erhält. Das gilt im Grunde genommen gleichermassen für die das Initiativkomitee bildenden Initianten wie für die Personen, welche die Initiative durch Unterschrift mittragen, wie auch für alle übrigen Stimmberechtigten.
4.5. Im vorliegenden Fall war die Unterschriftensammlung im Zeitpunkt der Ungültigerklärung abgeschlossen und das Zustandekommen der Volksinitiative bereits festgestellt. In der Folge bezog der Gemeinderat das Initiativkomitee in seinen Entscheidungsprozess zur Gültigkeitsprüfung mit ein. Die Initianten konnten sich dazu mit dem Gemeinderat austauschen und erhielten auch Kenntnis des von diesem eingeholten Gutachtens sowie die Gelegenheit, eine eigene Expertise einzureichen. Insbesondere fand dazu am 27. Februar 2020 eine ausserordentliche Gemeinderatssitzung statt, an der eine Delegation der Interessengemeinschaft teilnahm. In einem daran anschliessenden Schreiben teilte der Gemeinderat der Interessengemeinschaft mit, über die Gültigkeit der Initiative zu entscheiden, falls diese bis zum 16. März nicht zurückgezogen werde. Vor seinem Entscheid hatte der Gemeinderat die Initianten damit ausreichend angehört. Angesichts des vom Gemeinderat eingeholten Gutachtens und des erfolgten Meinungsaustausches konnte der Ungültigkeitsentscheid überdies für die Beschwerdeführer nicht unvorhersehbar und unerwartet ausgefallen sein. Insgesamt sind keine besonderen Umstände ersichtlich, welche die Einräumung weitergehender Parteirechte an die Initianten erfordert hätten. Es verstösst daher weder gegen das kantonale Recht noch gegen Verfassungsrecht, dass der Entscheid über die Ungültigerklärung den Beschwerdeführern nicht formell eröffnet wurde. Einen eigentlichen Rechtsnachteil, den sie nicht selbst zu verantworten hätten, erlitten sie dadurch nicht.
4.6. Was die Rüge des Verstosses gegen den Grundsatz von Treu und Glauben gemäss <ref-law> (sowie <ref-law>) durch den Gemeinderat betrifft, so durften die Beschwerdeführer aufgrund der Rechtslage auch nicht davon ausgehen, dass ihnen der Entscheid über die Ungültigerklärung mit Wirkung für den Fristbeginn formell eröffnet würde. Das von ihnen gestellte entsprechende Gesuch war für sich allein genauso wenig geeignet, den Beginn der Frist auszusetzen, wie der vom Gemeinderat gewährte Einbezug der Interessengemeinschaft in die Diskussionen um die Gültigkeit der Initiative. Die Gemeinde gab insbesondere nicht zu erkennen, dem Gesuch um formelle Eröffnung des Entscheids stattzugeben, was allenfalls zur irrtümlichen Einschätzung hätte führen können, die Beschwerdefrist beginne erst später zu laufen. Im Gegenteil teilte der Gemeinderat der Beschwerdeführerin 1 am 30. März 2020 ausdrücklich mit, eine förmliche Zustellung des Entscheids sei nicht vorgesehen. Da diese Information vorweg per Mail übermittelt wurde, war sie der Beschwerdeführerin 1 damit innert hängiger Frist bekannt. Als deren Vorstandsmitglieder müssen sich die beiden anderen Beschwerdeführer diese Kenntnis anrechnen lassen. Da zwischen dem Gesuch der Beschwerdeführer und der Antwort des Gemeinderats noch das Wochenende lag, lässt sich diesem auch nicht vorhalten, nicht rasch genug gehandelt zu haben, womit offenbleiben kann, ob er überhaupt verpflichtet gewesen wäre, innert der kurzen Beschwerdefrist zu antworten. Insgesamt hätten die Beschwerdeführer ausreichend Anlass und Gelegenheit gehabt, mit der Eventualität zu rechnen, dass ihnen der Entscheid nicht noch individuell zugestellt würde, und daher die Beschwerdeerhebung für den 30. März 2020 vorzubereiten, womit sie die Beschwerde rechtzeitig hätten einreichen können. Eine massgebliche Vertrauensgrundlage, auf die sie sich stützen könnten, bestand demnach nicht.
5.
5.1. Die Beschwerdeführer erachten es sodann als gesetzes- und verfassungswidrig, vom Beginn der Beschwerdefrist am 26. oder 27. März 2020 auszugehen. Sie hätten damals keine ausreichende Kenntnis vom Entscheid und von dessen Begründung gehabt, um ihn korrekt anfechten zu können.
5.2. Nach Art. 62 Abs. 2 GPR gibt es zwei Tatbestände, die den Beginn der Beschwerdefrist auslösen: die Entdeckung des Beschwerdegrundes oder die amtliche Veröffentlichung eines Ergebnisses. Wie dargelegt, gibt es bei der Ungültigerklärung einer Initiative kein amtliches Ergebnis im strengen Wortsinne; das Gesetz schreibt in diesem Fall auch keine amtliche Publikation vor. Aufgrund eines Analogieschlusses könnte aber vom Beginn des Fristenlaufs ausgegangen werden, wenn der Entscheid über die Ungültigerklärung tatsächlich amtlich publiziert wird (vgl. vorne E. 4.2). Davon geht in einer Subsidiärerwägung auch das Obergericht aus (E. 3.6 des angefochtenen Entscheids am Ende). Es hält jedoch insbesondere dafür, dass den Beschwerdeführern der Beschwerdegrund bereits mit der Zustellung der Medienmitteilung vom 26. März 2020 bekannt gewesen sei.
5.3. Zu prüfen ist zunächst, ob bzw. gegebenenfalls wann für die Beschwerdeführer im vorliegenden Verfahren der erste Tatbestand der Fristauslösung, d.h. die Entdeckung des Beschwerdegrunds, erfüllt war.
5.3.1. Von fristauslösenden Verhältnissen ist dann auszugehen, wenn in ausreichendem Masse das Erkenntnis des Entscheids und dessen Begründung bekannt werden, so dass in wirksamer Weise dagegen Beschwerde geführt werden kann. Im vorliegenden Fall stellte der Gemeinderat der Interessengemeinschaft (Beschwerdeführerin 1) seine Medienmitteilung per Mail unbestrittenermassen am 26. März 2020 zu. Bereits am gleichen Tag reagierte die Beschwerdeführerin 1 mit einer eigenen Medienmitteilung. Diese eigene Medienmitteilung war im Namen des Vereinsvorstands verfasst, dem die beiden Beschwerdeführer 2 und 3 als Vereinspräsidenten angehören. Alle drei Beschwerdeführer erhielten damit am 26. März 2020 Kenntnis von der Medienmitteilung des Gemeinderats. Das wird im Wesentlichen auch nicht bestritten.
5.3.2. Die Medienmitteilung des Gemeinderats gibt zwar nicht wörtlich den Entscheid desselben wieder. Sie beschreibt den Gemeinderatsbeschluss aber über zweieinhalb Seiten ausführlich. Es geht daraus genügend klar hervor, was der Gemeinderat beschlossen hat, nämlich die Ungültigkeit der Initiative, sowie auf welchen Gründen der Beschluss beruhte, nämlich "weil die Initiative ein Projekt (Doppelspur) verhindern will, auf das die Gemeinde Teufen rechtlich und finanziell nur beschränkten Einfluss ausüben kann." Dieser Zusammenhang wird im Text der Medienmitteilung weiter dargelegt und erläutert. Resultat und Begründung des Gemeinderatsentscheids werden darin ausreichend und originär dem Gemeinderat zuweisbar dargetan, so dass die Grundlage dafür bestand, in wirksamer Weise dagegen Beschwerde zu führen. Damit ist davon auszugehen, dass die Beschwerdeführer am 26. März 2020 rechtsgenüglich Kenntnis vom strittigen Entscheid über die Ungültigerklärung ihrer Initiative erhielten bzw. im Sinne von Art. 62 Abs. 2 GPR den Beschwerdegrund "entdeckten", womit die Beschwerdefrist zu laufen begann. Da es sich beim 26. März 2020 um einen Donnerstag handelte, womit die Frist bis am Montag, 30. März 2020, lief und die Beschwerdeführer keine weiteren Unterlagen zur Beschwerdeerhebung benötigten, standen ihnen sogar vier Tage zur Ausarbeitung der Beschwerde zur Verfügung. Im Übrigen kannten sie das Dossier von der Vorgeschichte her bereits bestens. Die rechtzeitige Beschwerdeerhebung war ihnen daher auch nicht aufgrund der konkreten Verhältnisse praktisch verunmöglicht.
5.4. Zwar kommt es auf eine spätere amtliche Publikation grundsätzlich nicht mehr an, wenn wie hier erstellt ist, dass die Beschwerdeführer bereits vorher oder zumindest gleichzeitig anderweitig Kenntnis vom Ungültigkeitsentscheid erhalten haben (vgl. das Urteil des Bundesgerichts 1C_203/2011 vom 1. Juli 2011 E. 2.1 und 2.5). Im vorliegenden Fall rechtfertigen sich aber dennoch zwecks Klärung der Rechtslage Erwägungen zum zweiten vom Obergericht bejahten Tatbestand, wonach der Ungültigkeitsentscheid in verbindlicher bzw. fristauslösender Weise amtlich publiziert worden sein soll. Nach Art. 38 GPR hat dies bei Wahlen und Abstimmungen so rasch wie möglich durch Anschlag zu erfolgen. Ob dies in analoger Weise auf einen Entscheid über die Ungültigkeit einer Initiative übertragen werden kann, braucht hier nicht entschieden zu werden, da von keiner Seite geltend gemacht wird, der strittige Gemeinderatsbeschluss sei unverzüglich ausgehängt worden. In Frage kommt mithin einzig eine amtliche Veröffentlichung in einem Publikationsorgan.
5.4.1. In der Appenzeller Zeitung vom 27. März 2020 erschien ein auf der Medienmitteilung des Gemeinderats Teufen vom Vortag beruhender Artikel über die Ungültigerklärung der fraglichen Doppelspur-Initiative. Die Appenzeller Zeitung ist von der Gemeinde Teufen als amtliches Publikationsorgan anerkannt. Es erscheint jedoch fraglich, ob ein redaktioneller Artikel der Zeitung als amtliche Veröffentlichung genügt. Zwar stützte sich dieser auf die Medienmitteilung des Gemeinderats. Für die Leserschaft ist aber bei einem redaktionell aufbereiteten Artikel nicht ohne weiteres ersichtlich, welcher Inhalt von der Gemeinde stammt und welcher vom verfassenden Journalisten. Eine korrekte amtliche Publikation setzt die wörtliche oder zumindest als solche erkennbare und damit direkt der Gemeinde zuzuordnende Wiedergabe eines zu veröffentlichenden Entscheids voraus. Schon deswegen kann im vorliegenden Fall die Beschreibung des fraglichen Beschlusses in der Appenzeller Zeitung nicht als amtliche Publikation gelten. Abgesehen davon stellt sich die Frage, ob eine solche Publikation nicht in Analogie zu Art. 38 GPR einen Hinweis auf die Beschwerdefrist und die Beschwerdeinstanz zu enthalten hätte, was hier nicht erfüllt wäre, aber offenbleiben kann, da ohnehin nicht von einer fristauslösenden amtlichen Veröffentlichung auszugehen ist.
5.4.2. Nach der Rechtsprechung kann überdies eine sehr kurze, namentlich eine dreitägige, Beschwerdefrist unzulässig sein, wenn dadurch aufgrund der konkreten, insbesondere zeitlichen Verhältnisse, etwa wegen des dazwischen liegenden Wochenendes, eine Beschwerdeerhebung praktisch verunmöglicht wird (vgl. vorne E. 3.2 sowie das Urteil des Bundesgerichts 1C_577/2013 vom 2. Oktober 2013 E. 2 und 3 in: ZBl 115/2014 S. 512). Im vorliegenden Fall erschien der Zeitungsartikel am Freitag, dem 27. März 2020, womit die dreitägige Frist am darauf folgenden Montag, dem 30. März 2020, abgelaufen wäre. Wer sich also aufgrund des Zeitungsartikels den Entscheid des Gemeinderats oder wenigstens die Medienmitteilung im Originaltext beschaffen wollte, um über eine allfällige Beschwerdeerhebung zu befinden, wäre vor grösseren zeitlichen Problemen gestanden. Die fragliche Medienmitteilung findet sich zwar heute auf dem Internet; ob und wann sie damals von der Gemeinde öffentlich zugänglich hochgeladen worden wäre, ist aber unbekannt. Unter diesen Umständen kann nicht davon ausgegangen werden, der Entscheid über die Ungültigerklärung der Doppelspur-Initiative sei korrekt in der Weise amtlich publiziert worden, dass die Beschwerdefrist für alle Stimmberechtigten vor dem 30. März 2020 zu laufen begonnen hätte.
5.5. Was die Beschwerdeführer sonst noch vorbringen, vermag eine Rechtsverletzung ebenfalls nicht zu belegen. Der Entscheid, die Fristeinreichung am 2. April 2020 sei verspätet erfolgt, ist demnach nicht rechtswidrig.
6.
Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang werden die Beschwerdeführer unter Solidarhaft kostenpflichtig (Art. 66 Abs. 1 und 5, <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 1'000.-- werden den Beschwerdeführern unter Solidarhaft auferlegt.
3.
Dieses Urteil wird den Beschwerdeführern, dem Gemeinderat Teufen, dem Regierungsrat des Kantons Appenzell Ausserrhoden und dem Obergericht des Kantons Appenzell Ausserrhoden, 4. Abteilung, schriftlich mitgeteilt.
Lausanne, 23. November 2021
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kneubühler
Der Gerichtsschreiber: Uebersax