Erwägungen:
1. Am 11. September 2001 schlossen A._ und B._ (Kläger und Beschwerdeführer) als Mieter mit der X._ AG (Beklagte und Beschwerdegegnerin) als Vermieterin einen Vertrag über eine 4 1/2-Zimmerwohnung in der Liegenschaft C._ mit Mietbeginn am 1. Januar 2002. Als monatlicher Mietzins wurden Fr. 1'380.-- zuzüglich Fr. 120.-- für einen Garageplatz und Fr. 195.-- à-conto Nebenkosten, total Fr. 1'695.-- vereinbart. Am 10. Januar 2002 kündigte die Beklagte den Klägern auf amtlichem Formular, das den Hinweis auf die Anfechtungsmöglichkeit der Vertragsänderung enthielt, eine Mietvertragsänderung mit Wirkung ab dem 1. April 2002 an. Der monatliche Mietzins wurde auf Fr. 1'620.-- erhöht und die à-conto-Zahlungen für Nebenkosten wurden auf Fr. 190.-- reduziert, so dass sich bei unverändertem Zins für die Garage ein monatlicher Mietzins von Fr. 1'930.-- ergab. Am 26. Januar 2006 kündigte die Beklagte den Mietvertrag auf amtlichem Formular auf den 30. April 2006.
1.1 Am 22. Mai 2006 beantragten die Kläger dem Kantonsgericht Zug, es sei festzustellen, dass die Mietzinserhöhung vom 10. Januar 2002 nichtig sei; die Beklagte sei zu verpflichten, ihnen die ab dem 1. April 2002 zu viel bezahlten Mietzinse in der Höhe von total Fr. 11'280.-- zuzüglich Zins zurückzuzahlen. In der Folge erhöhten sie ihre Forderung um weitere Fr. 2'400.--. Das Kantonsgericht Zug wies die Klage mit Urteil vom 15. März 2007 ab.
1.2 Mit Urteil vom 4. September 2007 wies das Obergericht des Kantons Zug die Berufung der Kläger ab und bestätigte das Urteil des Kantonsgerichts vom 15. März 2007. Das Obergericht stellte fest, dass die Erhöhung des Mietzinses vom 10. Januar 2002 wegen fehlender Unterschrift, vor allem aber wegen fehlender Begründung formnichtig gewesen war, kam jedoch zum Schluss, die Berufung der Kläger auf diesen Mangel sei rechtsmissbräuchlich.
1.3 Mit Beschwerde in Zivilsachen und subsidiärer Verfassungsbeschwerde stellen die Beschwerdeführer die Anträge, es sei das Urteil des Obergerichts des Kantons Zug vom 7. September 2007 aufzuheben (Ziffer 1) und festzustellen, dass die Mietzinserhöhung vom 10. Januar 2002 nichtig sei (Ziffer 2.a), und die Beschwerdegegnerin sei zu verpflichten, ihnen vom 1. April 2002 bis zum 28. Februar 2006 im Betrag von Fr. 11'280.-- und vom 1. März 2006 bis zum 1. Dezember 2006 im Betrag von Fr. 2'400.-- zuviel bezahlten Mietzins zuzüglich 5 % Verzugszins ab dem 1. März 2004 bzw. 1. Juli 2006 zu bezahlen (Ziffer 2b). Eventualiter sei das Verfahren zur Neubeurteilung an die Vorinstanz zurück zu weisen. Sie rügen, die Vorinstanz habe <ref-law> verletzt, indem sie ihnen Rechtsmissbrauch vorgeworfen habe, obwohl ihnen die Rechtsfolge der Nichtigkeit nicht bewusst gewesen sei; die Vorinstanz habe zu Unrecht die blosse Kenntnis des Mangels für die Annahme des Rechtsmissbrauchs als genügend angesehen.
1.4 Die Beschwerdegegnerin beantragt in der Antwort, die Beschwerde in Zivilsachen und die subsidiäre Verfassungsbeschwerde seien vollumfänglich abzuweisen und das angefochtene Urteil sei zu bestätigen.
2. Das angefochtene Urteil hat eine Zivilsache zum Gegenstand (<ref-law>). Die Beschwerde richtet sich gegen einen Endentscheid (<ref-law>) eines oberen kantonalen Gerichts (<ref-law>), mit dem die Begehren der Beschwerdeführer abgewiesen worden sind (<ref-law>). Da es sich um eine mietrechtliche Streitigkeit im Sinne von <ref-law> handelt, ist die Beschwerde in Zivilsachen zulässig, wenn der Streitwert mindestens Fr. 15'000.-- beträgt. Die strittige Forderung beträgt Fr. 13'680.--. Die Vorinstanz hat den Wert des Feststellungsbegehrens zudem so bemessen, dass der Streitwert insgesamt Fr. 15'000.-- beträgt. Der Streitwert ist damit erreicht, zumal die Beschwerdeführer die Kündigung angefochten haben (vgl. Urteil vom 2. November 2007 im Verfahren 4A_342/2007) und nicht festgestellt ist, wann die Beschwerdeführer die Wohnung verlassen haben. Die Voraussetzungen für die Beschwerde in Zivilsachen sind damit erfüllt und auf die subsidiäre Verfassungsbeschwerde ist nicht einzutreten.
3. Die Vorinstanz ist zutreffend davon ausgegangen, dass die den Beschwerdeführern am 10. Januar 2002 angekündigte Mietvertragsänderung den Formvorschriften nicht genügte und daher grundsätzlich nichtig ist. Sie hat indes die Berufung der Beschwerdeführer auf die Formnichtigkeit als rechtsmissbräuchlich erachtet.
3.1 Nach der Rechtsprechung ist die Berufung auf Formmängel vor allem dann rechtsmissbräuchlich, wenn das frühere Verhalten der Mieter bei der Vermieterin schutzwürdiges Vertrauen begründet und diese zu Handlungen veranlasst hat, die ihr angesichts der neuen Situation zu Schaden gereichen können. Dies ist insbesondere der Fall, wenn die Mieter in Kenntnis der Formvorschriften ausdrücklich auf deren Einhaltung verzichtet und die getroffene Vereinbarung freiwillig erfüllt haben (<ref-ruling> E. 3c S. 75 mit Hinweis).
3.2 Nach den Feststellungen im angefochtenen Entscheid teilten die Beschwerdeführer der Beschwerdegegnerin mit Schreiben vom 12. März 2002 unter anderem mit, gestützt auf eine Auskunft beim Mieterverband sollte die Mitteilung einer Mietzinserhöhung drei Monate und zehn Tage zum voraus und ausserdem zu den vertraglich bestimmten Terminen inklusive Begründung der Erhöhung erfolgen. Sie zeigten jedoch wegen der Wohnungsrenovation Verständnis für die Mietzinsanpassung und schlossen den Brief mit der Bemerkung, dass sie damit diese Angelegenheit als erledigt erachteten. In der Folge bezahlten sie ab dem 1. April 2002 monatlich den höheren Mietzins.
3.3 Die Vorinstanz hat zutreffend geschlossen, dass die Beschwerdeführer bei der Beschwerdegegnerin das begründete Vertrauen erweckten, die Erhöhung sei von ihnen akzeptiert worden, indem sie damals ihre Ansprüche nicht weiter verfolgten, in ihrem Schreiben vom März 2002 abschliessend festhielten, sie erachteten die Angelegenheit als erledigt und danach während rund vier Jahren den höheren Mietzins vorbehaltlos bezahlten. Da nach den Feststellungen der Vorinstanz keine Anhaltspunkte dafür bestehen, dass der Mietzins objektiv missbräuchlich gewesen sein könne, und die Formungültigkeit von den Beschwerdeführern erst nach der von ihnen als missbräuchlich erachteten Kündigung des Mietvertrags geltend gemacht wurde, hat die Vorinstanz die Berufung der Beschwerdeführer auf den Formmangel zutreffend als rechtsmissbräuchlich erachtet.
3.4 Die Vorbringen der Beschwerdeführer ändern daran nichts. Dass sie Kenntnis des Mangels hatten, ist für das Bundesgericht verbindlich festgestellt. Dass sie angeblich keine Kenntnis über die Rechtsfolge der Formnichtigkeit hatten bzw. ihnen die Unverbindlichkeit der angezeigten Erhöhung nicht bewusst war, hat die Vorinstanz im vorliegenden Fall zutreffend für unerheblich gehalten. Denn nach den Feststellungen im angefochtenen Entscheid haben sich die Beschwerdeführer auf eine Auskunft des Mieterverbands berufen und enthielt das amtliche Formular, auf dem ihnen die Erhöhung angezeigt wurde, den Hinweis auf die Anfechtungsmöglichkeit der Vertragsänderung. Wenn sie unter diesen Umständen in Kenntnis des Mangels und der Anfechtungsmöglichkeit auf die Anfechtung verzichteten und erklärten, die Angelegenheit sei für sie erledigt, haben sie die Beschwerdegegnerin davon abgehalten, eine formgültige Erhöhung auf den nächsten Termin anzuzeigen. Dabei ist ohne Bedeutung, dass die vorgeschriebene Form nicht nur wegen fehlender Begründung, sondern auch wegen fehlender Unterschrift nicht eingehalten war.
4. Die subsidiäre Verfassungsbeschwerde ist - da die Beschwerde in Zivilsachen gegeben ist - unzulässig. Es ist darauf nicht einzutreten. Die Beschwerde in Zivilsachen ist als unbegründet abzuweisen. Die Gerichtskosten sind bei diesem Verfahrensausgang den Beschwerdeführern aufzuerlegen (<ref-law>). Sie haben der anwaltlich vertretenen Beschwerdegegnerin deren Parteikosten für das vorliegende Beschwerdeverfahren zu ersetzen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
2. Die Beschwerde in Zivilsachen wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit und intern je zur Hälfte auferlegt.
4. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit und intern je zur Hälfte mit Fr. 1'500.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zug, Zivilrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 14. Januar 2008
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Corboz Hürlimann