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 Art. 29 Abs. 2 BV, von Art. 343 Abs. 4, Art. 357 Abs. 1 und Art. 356 Abs. 1 i.V.m. Art. 112 OR sowie von Art. 2 Abs. 2 ZGB 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.