Sachverhalt:
A. Am 13. Juni 2008 beschloss die Bundesversammlung die Genehmigung und die Umsetzung des Notenaustauschs zwischen der Schweiz und der Europäischen Gemeinschaft betreffend die Übernahme der Verordnung (EG) Nr. 2252/2004 über biometrische Pässe und Reisedokumente. Gegen diesen Bundesbeschluss wurde das Referendum ergriffen. An der Volksabstimmung vom 17. Mai 2009 wurde der Bundesbeschluss mit 953'136 Ja-Stimmen (50.14 %) gegen 947'632 Nein-Stimmen (49.86 %) angenommen.
Mit weitgehend gleichlautenden Eingaben erhoben Federico Guglielmino, Thomas Horath, Beatrice Krähenbühl-Amstutz, Kaspar Kunz und Gerda Weber beim Regierungsrat des Kantons Zug Abstimmungsbeschwerden gemäss Art. 77 Abs. 1 lit. b des Bundesgesetzes vom 17. Dezember 1976 über die politischen Rechte (BPR; SR 161.1). Der Regierungsrat trat auf die Beschwerden mit Beschlüssen vom 2. Juni 2009 nicht ein.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 8. Juni 2009 beantragen Federico Guglielmino, Thomas Horath, Beatrice Krähenbühl-Amstutz, Kaspar Kunz und Gerda Weber im Wesentlichen, die Beschlüsse des Regierungsrats seien insoweit aufzuheben, als den Beschwerdeführern Kosten in der Höhe von Fr. 300.-- auferlegt worden seien. Es sei festzustellen, dass die Beschwerdeführer legitimiert seien, beim Regierungsrat des Kantons Zug Beschwerde einzureichen. Die Abstimmungsbeschwerden seien für gültig zu erklären und zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Subsidiär werde Verfassungsbeschwerde erhoben.
Der Regierungsrat beantragt in seiner Stellungnahme vom 29. Juni 2009 die Abweisung der Beschwerde. Die ebenfalls zur Stellungnahme eingeladene Bundeskanzlei liess sich nicht vernehmen.
C. Die I. öffentlich-rechtliche Abteilung des Bundesgerichts hat die Angelegenheit am 1. Oktober 2009 an einer öffentlichen Sitzung beraten.

Erwägungen:
1. 1.1 Angefochten sind (im Wesentlichen gleichlautende) Nichteintretensentscheide in einer Stimmrechtssache unter Auferlegung der Verfahrenskosten. Dagegen ist die Beschwerde nach Art. 82 lit. c BGG zulässig (<ref-ruling> E. 3 S. 144 mit Hinweisen; Urteil 2C_700/2008 vom 18. Juni 2009 E. 1.2). Der Regierungsrat ist Vorinstanz im Sinne von Art. 88 Abs. 1 lit. b BGG. Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist unter Vorbehalt der nachfolgenden Erwägung einzutreten. Für die von den Beschwerdeführern eventualiter erhobene subsidiäre Verfassungsbeschwerde besteht demnach kein Raum (Art. 113 BGG).
1.2 Die Beschwerdeführer beantragen, es sei festzustellen, dass sie legitimiert seien, vor dem Regierungsrat des Kantons Zug Beschwerde zu führen. Ein Interesse an einer derartigen Feststellung, welches über das Interesse an der Gutheissung der übrigen Rechtsbegehren hinausgeht, wird nicht dargetan und ist auch nicht erkennbar. Auf das Feststellungsbegehren ist nicht einzutreten (<ref-ruling> E. 1c S. 491; Urteil 1C_45/2009 vom 6. Juli 2009 E. 1.5; je mit Hinweisen).
2. 2.1 Die Beschwerdeführer machen geltend, eine Abstimmungsbeschwerde gemäss Art. 77 Abs. 1 lit. b BPR könne unabhängig vom Wohnsitz im betreffenden Kanton erhoben werden. Der Regierungsrat des Kantons Zug sei deshalb zu Unrecht nicht auf ihre Beschwerden eingetreten. In diesem Zusammenhang rügen die Beschwerdeführer auch den Kostenentscheid der Vorinstanz. Der Regierungsrat erklärte es im angefochtenen Entscheid als nicht nachvollziehbar, weshalb die Beschwerdeführer im Kanton Zug Beschwerde erhoben hätten, und auferlegte ihnen je Gerichtskosten in der Höhe von Fr. 300.--.
2.2 Die Frage, ob eine Abstimmungsbeschwerde gemäss Art. 77 Abs. 1 lit. b BPR nur bei der Kantonsregierung am eigenen Wohnsitz erhoben werden kann, ist vom Bundesgericht bisher nicht beantwortet worden. Die Ansichten in der Literatur sind geteilt. ETIENNE GRISEL und CHRISTOPH HILLER weisen darauf hin, dass letztlich das gesamtschweizerische Resultat entscheidend sei. Jeder Stimmbürger habe ein Interesse daran, dass dieses nicht verfälscht werde, unabhängig davon, in welchem Kanton die behaupteten Unregelmässigkeiten aufträten (ETIENNE GRISEL, Initiative et référendum populaires, 3. Aufl. 2004, S. 138 Rz. 319; CHRISTOPH HILLER, Die Stimmrechtsbeschwerde, 1990, S. 26 f.). Die gegenteilige Auffassung vertreten WALTER STUTZ und CHRISTOPH WINZELER unter Berufung auf den Zusammenhang zwischen der Stimmberechtigung und der Beschwerdelegitimation (vgl. Art. 39 Abs. 2 Satz 1 BV, Art. 3 Abs. 1 BPR; WALTER STUTZ, Rechtspflege, in: Das Bundesgesetz über die politischen Rechte, 1978, S. 123; CHRISTOPH WINZELER, Die politischen Rechte des Aktivbürgers nach schweizerischem Bundesrecht, 1983, S. 146).
Ausschlaggebend für den Erfolg einer Abstimmungsbeschwerde ist das Vorliegen von Unregelmässigkeiten, die geeignet waren, das Hauptresultat (das heisst in diesem Fall: das gesamtschweizerische Resultat) der Abstimmung zu beeinflussen (Art. 79 Abs. 2bis BPR). Ist es in irgendeinem Kanton zu derartigen Unregelmässigkeiten gekommen, so verletzt dies mit Blick auf das allein ausschlaggebende Hauptresultat das Stimmrecht eines jeden Stimmberechtigten. Ob infolgedessen nicht jeder Stimmberechtigte unabhängig von seinem Wohnsitz Beschwerde führen können muss, kann jedoch offen gelassen werden, denn die materiellen Rügen der Beschwerdeführer erweisen sich als unbegründet, wie im Folgenden aufzuzeigen ist (E. 3 hiernach).
2.3 In Bezug auf den Kostenentscheid der Vorinstanz erweist sich die Rüge der Beschwerdeführer indessen klar als begründet. Gemäss Art. 86 Abs. 1 BPR dürfen für Amtshandlungen aufgrund des Bundesgesetzes über die politischen Rechte keine Kosten erhoben werden. Nur bei trölerischen oder gegen den guten Glauben verstossenden Beschwerden können die Kosten dem Beschwerdeführer überbunden werden (vgl. <ref-ruling>; Urteile 8C_903/2008 vom 27. März 2009 E. 4, in: Anwaltsrevue 2009 6 S. 333; 2A.507/2006 vom 15. Januar 2007 E. 1.3, in: sic! 5/2007 S. 353; je mit Hinweisen). Nur schon aufgrund der divergierenden Meinungen in der Literatur kann von Trölerei und nicht gutgläubigem Prozessieren nicht die Rede sein. Der Kostenentscheid ist deshalb aufzuheben.
3. 3.1 In der Sache rügen die Beschwerdeführer den knappen Ausgang der eidgenössischen Abstimmung als Unregelmässigkeit im Sinne von Art. 77 Abs. 1 lit. b BPR. Im kantonalen Verfahren hatten sie beantragt, das Abstimmungsresultat im Kanton Zug als ungültig zu erklären, eventuell eine Nachzählung anzuordnen.
Eine Nachzählung auf Grund eines knappen Gesamtresultats müsste zwangsläufig in allen Kantonen erfolgen, unabhängig davon, wie das jeweilige kantonale Resultat ausfiel. Ein Begehren auf eine schweizweite Nachzählung haben aber die Beschwerdeführer weder im kantonalen noch im bundesgerichtlichen Verfahren gestellt. Auf ihre das knappe Hauptresultat betreffenden Ausführungen ist daher nicht einzugehen.
3.2 Im Übrigen beschränken sich die Beschwerdeführer im Verfahren vor Bundesgericht darauf, die Aufhebung des angefochtenen kantonalen Entscheides sowie die Rückweisung der Sache an die Vorinstanz zur neuen Beurteilung zu beantragen. Ein solcher kassatorischer Antrag ist im Rahmen der Beschwerde in öffentlich-rechtlichen Angelegenheiten grundsätzlich zulässig (<ref-ruling> E. 1.4 S. 414 f. mit Hinweisen). Zu beachten ist weiter, dass sich die hier zu beurteilende Beschwerde gegen einen Nichteintretensentscheid richtet und im Falle der Unzulässigkeit eines kassatorischen Antrags der Instanzenzug verkürzt würde. Dennoch rechtfertigt sich bei Abstimmungsbeschwerden im Sinne von Art. 77 Abs. 1 BPR, auf welche eine Kantonsregierung nicht eingetreten ist, eine ausgeprägtere Formstrenge. Angesichts des Umstands, dass gegen Abstimmungs- und Wahlresultate gerichtete Beschwerden ohne Verzug zu behandeln sind (vgl. Art. 79 Abs. 1 BPR; vgl. auch Art. 77 Abs. 2 BPR und Art. 100 Abs. 3 lit. b BGG) und zumal das Bundesgericht auch im vorliegenden Fall reformatorisch entscheiden kann (Art. 107 Abs. 2 BGG), konnten die Beschwerdeführer nicht ohne weiteres mit einer Rückweisung der Sache rechnen. Sie wären gehalten gewesen, Anträge zur Sache und eine entsprechende Begründung im Verfahren vor Bundesgericht vorzubringen. Dem Rückweisungsantrag ist daher nicht stattzugeben.
Indessen sind die von den Beschwerdeführern im kantonalen Verfahren erhobenen Rügen ausnahmsweise aus Gründen von Treu und Glauben (Art. 5 Abs. 3 und Art. 9 BV) vom Bundesgericht materiell zu behandeln. Denn die dargelegte Rechtslage, wonach sich ein Beschwerdeführer im bundesgerichtlichen Verfahren auch dann nicht auf einen kassatorischen Antrag beschränken darf, wenn eine Kantonsregierung auf eine Beschwerde nach Art. 77 Abs. 1 BPR nicht eingetreten ist, war bisher nicht ausreichend klar (<ref-ruling> E. 1.2.3 S. 274 f. mit Hinweisen).
3.3 Die Beschwerdeführer machten vor der Vorinstanz geltend, die veröffentlichten Abstimmungszahlen erlaubten keinen Rückschluss auf den Anteil der brieflichen Stimmabgabe. Auch der schwerwiegende Fehler im Wahlbüro von Embrach und der Wahlbetrugsversuch in Trimbach zeigten die Notwendigkeit einer Nachzählung. Beim Wägen der Stimmzettel stellten Änderungen in der Luftfeuchtigkeit und der Temperatur eine zusätzliche Fehlerquelle dar. Weiter seien die Wahlkuverts keiner einwandfrei protokollierten und lückenlosen Überwachung bis zur Auszählung unterstanden. Es bestehe keine Kontrolle darüber, ob nicht Wahlkuverts auf Grund des Namens des Stimmenden unterschlagen worden seien. Schliesslich sei davon auszugehen, dass nicht alle Nebenurnen aufgestellt worden seien, insbesondere in Altersheimen.
Wie der Regierungsrat in seiner Vernehmlassung zu Recht darlegt, beschränken sich die Beschwerdeführer mit diesen Vorbringen auf das pauschale Geltendmachen möglicher Unregelmässigkeiten bei der Abstimmung. Vorab ist festzuhalten, dass es keine Unregelmässigkeit darstellt, wenn der Anteil der brieflichen Stimmabgabe nicht publiziert wird. Sodann betreffen die von den Beschwerdeführern angeführten Vorfälle in Embrach und Trimbach nicht den Kanton Zug. Mit der Behauptung, die Wahlkuverts seien nicht lückenlos überwacht worden und hätten teilweise unterschlagen werden können, geben die Beschwerdeführer keinerlei konkrete Hinweise auf eine fehlerhafte Auszählung oder gesetzeswidriges Verhalten. Dasselbe gilt für das Vorbringen, Änderungen in der Luftfeuchtigkeit und der Temperatur könnten beim Wägen der Stimmzettel das Resultat verfälschen. Auf solche konkrete Hinweise kann jedoch nicht gänzlich verzichtet werden, soweit sich die Beschwerdeführer auf eigentliche Unregelmässigkeiten berufen (<ref-ruling> E. 3.3 S. 449; Urteil 1C_275/2009 vom 1. Oktober 2009 E. 2; je mit Hinweisen). Auch die Behauptung, es seien nicht alle "Nebenurnen" aufgestellt worden, wird nicht näher ausgeführt. Damit erweisen sich die vor dem Regierungsrat vorgetragenen Rügen als unbegründet.
4. Zusammenfassend ergibt sich, dass der Regierungsrat des Kantons Zug den Beschwerdeführern zu Unrecht Kosten auferlegt hat. In der Hauptsache erweist sich die Beschwerde indessen als unbegründet. Die Beschwerde ist deshalb teilweise gutzuheissen und die angefochtenen Entscheide sind im Kostenpunkt aufzuheben. Im Übrigen ist die Beschwerde abzuweisen, soweit darauf einzutreten ist.
Es ist gerechtfertigt, auf die Erhebung von Gerichtskosten zu verzichten (Art. 66 Abs. 1 BGG). Die nicht anwaltlich vertretenen Beschwerdeführer haben keinen Anspruch auf eine Parteientschädigung (Art. 68 Abs. 1 und 2 BGG; <ref-ruling> E. 4 S. 446 mit Hinweis).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen. Die Dispositiv-Ziffern 2 der angefochtenen Beschlüsse werden aufgehoben. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf eingetreten wird.
2. Es werden keine Gerichtskosten erhoben.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, dem Regierungsrat des Kantons Zug und der Bundeskanzlei schriftlich mitgeteilt.
Lausanne, 1. Oktober 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold