Sachverhalt:
A. A._ (Kläger und Beschwerdeführer 1), B._ (Kläger und Beschwerdeführer 2), C._ (Kläger und Beschwerdeführer 3) und D._ (Kläger und Beschwerdeführer 4) waren zwischen dem 1. Oktober 2003 und dem 30. April 2007 während unterschiedlichen Zeiträumen bei der X._ AG (Beklagte, Beschwerdegegnerin) angestellt. Zu Beginn ihres Arbeitsverhältnisses waren sie nicht Mitglied der Gewerkschaft SYNA, wurden es aber - mit Ausnahme des Beschwerdeführers 1 - im Verlauf ihrer Anstellung. Die Beschwerdegegnerin ihrerseits ist seit dem Jahr 1998 Mitglied des Arbeitgeberverbandes der Schweizer Maschinenindustrie (Swissmem, im Folgenden ASM).
A.a Die Sozialpartner in der Maschinen-, Elektro- und Metallindustrie, darunter der ASM und die SYNA, hatten auf den 1. Januar 2006 eine neue Gesamtarbeitsvereinbarung abgeschlossen, die diejenige der Jahre 1998 bis 2005 ersetzte. Die neue Vereinbarung (im Folgenden GAV) gilt bis zum 31. Dezember 2010. Durch ihre Mitgliedschaft beim ASM war die Beschwerdegegnerin demnach auch an den neuen GAV gebunden.
A.b Nach Art. 12.1 des ab 1. Januar 2006 gültigen GAV beträgt die wöchentliche Arbeitszeit 40 Stunden. Nach dem jeweiligen Einzelarbeitsvertrag der Beschwerdeführer und dem Personal-Reglement betrug die wöchentliche Arbeitszeit im Betrieb der Beschwerdegegnerin hingegen 41,5 Stunden.
A.c Nachdem die Beschwerdeführer die Mitgliedschaft bei der SYNA erworben hatten, wurden sie auf die unterschiedlichen Arbeitszeiten im GAV und im Personal-Reglement aufmerksam gemacht. Vorher waren sich die Parteien der Existenz des GAV offenbar nicht bewusst. Gespräche über eine nachträgliche Anerkennung der nach Ansicht der Beschwerdeführer zu viel geleisteten Arbeit als entschädigungspflichtige Überstunden führten zu keiner Einigung.
B. Am 28. Juni 2007 erhoben die Beschwerdeführer beim Einzelrichter des Kantonsgerichts des Kantons Appenzell Ausserrhoden Klage mit dem Rechtsbegehren, die Beschwerdegegnerin sei zu verpflichten, jedem Beschwerdeführer einen anhand der jeweils geleisteten Überstunden berechneten Betrag plus Zins zu bezahlen.
Mit Urteil vom 6. November 2007 wies der Einzelrichter die Klage des Beschwerdeführers 1 ab. Die Klagen der Beschwerdeführer 2 bis 4 hiess er insofern teilweise gut, als er ihnen ab ihrer Mitgliedschaft bei der SYNA eine Vergütung für die geleisteten Mehrstunden zusprach.
C. Gegen das Urteil des Einzelrichters erhoben die Beschwerdeführer Appellation, die der Einzelrichter des Obergerichts von Appenzell Ausserrhoden mit Entscheid vom 25. Januar 2008 hinsichtlich der Beschwerdeführer 1, 2 und 4 abwies. Die Appellation des Beschwerdeführers 3 wurde teilweise gutgeheissen. Der Einzelrichter kam zum Schluss, dass der (nicht allgemein verbindlich erklärte) GAV erst mit dem jeweiligen Beitritt der Beschwerdeführer zur Gewerkschaft SYNA auf sie Anwendung gefunden habe, und verneinte in diesem Zusammenhang den Abschluss eines Vertrags zu Gunsten Dritter, die Übernahme der Bestimmungen des GAV in den Einzelarbeitsvertrag auf Grund der Einziehung des Solidaritätsbeitrags, ein rechtsmissbräuchliches Verhalten der Beschwerdegegnerin sowie die rückwirkende Anerkennung von GAV-Ansprüchen durch das Verhalten der Beschwerdegegnerin.
D. Mit Beschwerde in Zivilsachen vom 27. Februar 2008 beantragen die Beschwerdeführer dem Bundesgericht, die Beschwerdegegnerin sei in Abänderung des Entscheids des Einzelrichters am Obergericht von Appenzell Ausserrhoden vom 25. Januar 2008 zu verpflichten, den Beschwerdeführern zu bezahlen:
1. Dem Beschwerdeführer 1 Fr. 6'977.60 nebst Zins zu 5 % seit 1. April 2006
2. Dem Beschwerdeführer 2 zusätzlich Fr. 7'562.80 nebst Zins zu 5 % seit 1. Januar 2007
3. Dem Beschwerdeführer 3 zusätzlich Fr. 6'439.20 nebst Zins zu 5 % seit 1. Januar 2007
4. Dem Beschwerdeführer 4 zusätzlich Fr. 1'673.-- nebst Zins zu 5 % sei 1. Mai 2007.
Die Beschwerdeführer machen eine Verletzung von Art. 9 und <ref-law>, von Art. 343 Abs. 4, Art. 357 Abs. 1 und Art. 356 Abs. 1 i.V.m. <ref-law> sowie von <ref-law> geltend.
E. Die Beschwerdegegnerin beantragt in ihrer Vernehmlassung die Abweisung der Beschwerde, soweit darauf einzutreten ist. Der Einzelrichter des Obergerichts verzichtet unter Verweis auf die Ausführungen im angefochtenen Urteil auf Gegenbemerkungen.

Erwägungen:
1. 1.1 In arbeitsrechtlichen Streitigkeiten ist die Beschwerde in Zivilsachen nach <ref-law> nur zulässig, wenn der Streitwert mindestens Fr. 15'000.-- beträgt. Der Streitwert bestimmt sich gemäss <ref-law> nach den Begehren, die vor der Vorinstanz streitig geblieben sind. <ref-law> hält darüber hinaus fest, dass mehrere in einer vermögensrechtlichen Sache von Streitgenossen geltend gemachte Begehren zusammengerechnet werden, sofern sie sich nicht gegenseitig ausschliessen. Diese Regel wurde aus Art. 47 Abs. 1 aOG übernommen und die dazu ergangene Rechtsprechung behält auch unter dem BGG ihre Gültigkeit (Urteil 4A_438/2007 vom 29. Januar 2008 E. 1.2). Danach ist die Zusammenrechnung zulässig, sofern die Begehren im kantonalen Verfahren vereinigt wurden und in diesem Verfahren Gegenstand eines einzigen Urteils waren. Bei der subjektiven Klagehäufung müssen die Kläger bzw. die Beklagten darüber hinaus Streitgenossen im Sinn von <ref-law> sein. Nach Abs. 2 lit. b dieser Norm können mehrere Personen in der gleichen Klage als Kläger auftreten oder als Beklagte belangt werden, wenn gleichartige, auf einem im Wesentlichen gleichartigen tatsächlichen und rechtlichen Grund beruhende Ansprüche den Streitgegenstand bilden (<ref-ruling> E. 6a S. 70).
Diese Voraussetzungen sind vorliegend erfüllt. Die Beschwerdeführer verlangen von der Beschwerdegegnerin die nachträgliche Bezahlung von Überstunden gestützt auf den GAV; dabei schadet es nicht, dass die Zeiträume, für die die einzelnen Ansprüche geltend gemacht werden, nicht vollständig übereinstimmen (Urteil 4C.238/1993 vom 26. Oktober 1993 E. 1b). Die Zusammenrechnung der Begehren ergibt einen Streitwert von Fr. 22'652.60. Auf die Beschwerde in Zivilsachen ist damit grundsätzlich einzutreten.
1.2 Gegen Appellationsentscheide des Einzelrichters des Obergerichts von Appenzell Ausserrhoden kann gestützt auf <ref-law> AR Rechtsverweigerungsbeschwerde wegen Willkür erhoben werden (Max Ehrenzeller, Zivilprozessordnung des Kantons Appenzell A.Rh. vom 27. April 1980, N. 4 zu <ref-law> AR). Soweit die Beschwerdeführer bei der Feststellung des Sachverhalts oder bei der Begründung des Entscheids eine Verletzung von <ref-law> geltend machen, kann darauf mangels Erschöpfung des Instanzenzuges nicht eingetreten werden.
2. Die Beschwerdeführer rügen zunächst eine Verletzung des rechtlichen Gehörs für den Fall, dass die Feststellung der Vorinstanz, den Vertragsparteien sei bis Ende 2006 nicht bewusst gewesen, dass der GAV existiere, tatsächlich - wie in E. 2.2.1.3 des angefochtenen Entscheides dargelegt - anhand des Protokolls der Hauptverhandlung des erstinstanzlichen Richters getroffen worden sei.
2.1 Der aus <ref-law> fliessende Anspruch auf rechtliches Gehör dient einerseits der Sachaufklärung und stellt anderseits ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines solchen Entscheids zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen (<ref-ruling> E. 3.1 S. 370 f. mit Hinweisen).
2.2 Der erstinstanzliche Richter hielt in seinem Entscheid fest, beide Parteien hätten anlässlich der Hauptverhandlung ausführen lassen, dass ihnen die Existenz des GAV nicht bewusst gewesen sei. Die Vorinstanz bezog sich in lit. B der Sachverhaltsschilderung und in E. 2.2.2.3 bzw. E. 2.2.3.3 auf dieses Zugeständnis an der Hauptverhandlung. Wie die Vorinstanz in ihrem Entscheid ausführt, macht sich der Richter in Appenzell Ausserhoden nach ständiger Praxis in einem einzelrichterlichen Verfahren Handnotizen von den wesentlichsten Vorbringen der Parteien. In der Regel werden sodann die wesentlichsten Aussagen der Parteien im Entscheid kurz zusammengefasst wiedergegeben. Soweit die Vorinstanz in E. 2.2.1.3 ihres Entscheids mit dem dort erwähnten "Protokoll" derartige Handnotizen des Einzelrichters gemeint haben sollte, hat sie aus diesen jedenfalls nichts anderes abgeleitet, als bereits im erstinstanzlichen Entscheid festgehalten wird. Eine Verletzung des rechtlichen Gehörs liegt nicht vor.
3. Die Beschwerdeführer machen weiter geltend, die Vorinstanz habe zu Unrecht das Bestehen eines Vertrags zugunsten eines Dritten verneint. Sie vertreten die Auffassung, die Beschwerdegegnerin sei durch den Abzug der Solidaritätsbeiträge und deren Ablieferung an den Arbeitgeberverband in eine vertragliche Beziehung zur GAV-Gemeinschaft (die Gemeinschaft aller vertragsschliessenden Verbände) getreten und habe damit einen Vertrag zugunsten Dritter abgeschlossen.
3.1 Hat sich jemand, der auf eigenen Namen handelt, eine Leistung an einen Dritten zu dessen Gunsten versprechen lassen, so ist er nach <ref-law> berechtigt zu fordern, dass an den Dritten geleistet werde. Der Dritte kann gestützt auf <ref-law> selbständig die Erfüllung fordern, wenn es die Willensmeinung der beiden anderen war, oder wenn es der Übung entspricht.
3.2 Nach den verbindlichen Feststellungen der Vorinstanz war der Beschwerdegegnerin die Existenz des GAV bis Ende 2006 nicht bewusst. Was die Beschwerdeführer dagegen vorbringen, kann nicht gehört werden (<ref-law> und oben E. 1.2). Sollten die Beschwerdeführer mit ihrem Hinweis auf den Anschein, den die Beschwerdegegnerin mit dem Abzug der Solidaritätsbeiträge gegenüber der "GAV-Gemeinschaft" geschaffen habe, die Auffassung vertreten, allein auf Grund des Abzugs und der Ablieferung der Solidaritätsbeiträge sei nach dem Vertrauensprinzip der Abschluss eines Vertrags zugunsten eines Dritten mit der "GAV-Gemeinschaft" anzunehmen, dessen Erfüllung der Dritte selbständig fordern könne, ist ihnen nicht zu folgen. Abgesehen davon, dass das angefochtene Urteil nicht feststellt, die "GAV-Gemeinschaft" habe das Verhalten der Beschwerdegegnerin in diesem Sinn verstanden, kann keinesfalls davon ausgegangen werden, dass sie es in guten Treuen so hätte verstehen dürfen und müssen. Schliesslich ist nicht ersichtlich, warum und inwiefern die Beschwerdeführer das Bundesgericht um Überprüfung der in <ref-ruling> wiedergegebenen Rechtsprechung ersucht, halten sie doch selber fest, dass sich der vorliegende Fall von der damals zu beurteilenden Konstellation unterscheidet.
4. Weiter machen die Beschwerdeführer geltend, es müssten für den Fall, dass kein Vertrag zugunsten Dritter vorliege, entweder die Einzelarbeitsverträge normativ ausgelegt werden oder aber es sei ein Anschluss an den GAV im Sinn von <ref-law> ohne Rücksicht auf die fehlende Schriftform gemäss <ref-law> anzunehmen, um eine Vergütung der geleisteten Überstunden zu ermöglichen.
4.1 Soweit die Beschwerdeführer aus dem Abzug der Solidaritätsbeiträge gestützt auf <ref-law> i.V.m. <ref-law> und <ref-law> auf eine entsprechende Absprache in den Einzelarbeitsverträgen schliessen will, kann ihnen schon deshalb nicht gefolgt werden, weil den Parteien nach den verbindlichen Feststellungen der Vorinstanz das Vorliegen des GAV bei Abschluss dieser Verträge gar nicht bewusst war.
4.2 Die Beschwerdeführer begründen ihre Auffassung, der Anschluss im Sinn von <ref-law> könne auch ohne die erforderliche Schriftform angenommen werden, damit, dass die Anrufung von <ref-law> durch die Beschwerdegegnerin als rechtsmissbräuchlich erscheine.
Die Partei, die der anderen Rechtsmissbrauch vorwirft, hat die besonderen Umstände nachzuweisen, auf Grund derer anzunehmen ist, dass Rechtsmissbrauch vorliegt (<ref-ruling> E. 2.1 S. 58 f.). Die Beschwerdeführer begründen den angeblichen Rechtsmissbrauch jedoch mit keinem Wort. Schon aus diesem Grund kann ihnen nicht gefolgt werden.
5. Nach dem Gesagten hat die Vorinstanz kein Bundesrecht verletzt, als sie mangels Rechtsgrundlage die Klage auf Zahlung von Überstundenentschädigungen für die Zeit vor dem Beitritt der Beschwerdeführer zur Gewerkschaft SYNA abwies. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer unter solidarischer Haftbarkeit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 2 und 4 BGG).

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 solidarischer Haftbarkeit auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 1'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergerichtspräsidenten von Appenzell Ausserrhoden schriftlich mitgeteilt.
Lausanne, 16. April 2008
Im Namen der I. zivilrechtlichen Abteilung des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Corboz Hürlimann