Sachverhalt:
A. A._ und B._ (Beschwerdeführer 1) bewohnen eine 41⁄2-Zimmerwohnung an der D._-Strasse 308 in Basel. C._ (Beschwerdeführerin 2) ist Mieterin einer 21⁄2- Zimmerwohnung an der D._-Strasse 310 in Basel. Aufgrund einer Sanierung im Jahre 2002 zeigte die X._ Gesellschaft (Beschwerdegegnerin), vertreten durch ihre Tochtergesellschaft X._ Immobilien AG, am 7. November 2003 Mietzinserhöhungen an, den Beschwerdeführern 1 von Fr. 1'204.-- auf Fr. 1'314.--, der Beschwerdeführerin 2 von Fr. 717.-- auf Fr. 798.--. Nachdem vor der Schlichtungsstelle keine Einigung erzielt werden konnte, gelangte die Beschwerdegegnerin an das Zivilgericht Basel-Stadt und beantragte, die Mietzinse entsprechend den bekanntgegebenen Erhöhungen festzusetzen. Der Zivilgerichtspräsident hiess beide Klagen am 27. August 2007 gut. Die gegen diese Entscheide ergriffene kantonale Beschwerde wies das Appellationsgericht Basel-Stadt am 30. April 2008 ab.
B. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer im Wesentlichen, es sei festzustellen, dass die Mietzinserhöhungen missbräuchlich seien. Die Beschwerdegegnerin schliesst auf kostenfällige Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1. Die Beschwerdeführer sind der Auffassung, die Mietzinserhöhung sei nichtig, da sie nicht auf einem von der zuständigen Behörde genehmigten Formular erfolgt sei. Sowohl der Vertreter der Beschwerdeführer als auch der erstinstanzliche Richter hätten von der zuständigen Behörde die Auskunft erhalten, das verwendete Formular sei nicht genehmigt worden. Indem die kantonalen Instanzen dennoch von einem genehmigten Formular ausgingen, hätten sie sich eine Zuständigkeit angemasst, die ihnen nicht zukomme.
1.1 Die Vorinstanz hielt in tatsächlicher Hinsicht fest, die Tochtergesellschaft der Beschwerdegegnerin, welche diese vertreten hatte, habe ihre Firma geändert, aber noch unter der ursprünglichen Firma die Genehmigung für ein Erhöhungsformular erhalten. Daher sei sie nicht verpflichtet gewesen, nach dem Firmenwechsel eine erneute Genehmigung einzuholen, da es sich um dieselbe Rechtsperson handle, der das Formular bewilligt worden war.
1.2 Nach <ref-law> muss der Vermieter eine Mietzinserhöhung auf einem vom Kanton genehmigten Formular mitteilen und begründen. Die Mietzinserhöhung ist nichtig, wenn der Vermieter sie nicht mit dem vorgeschriebenen Formular mitteilt (<ref-law>). Das Formular für die Mitteilung von Mietzinserhöhungen muss nach Art. 19 der Verordnung über die Miete und Pacht von Wohn- und Geschäftsräumen vom 9. Mai 1990 (VMWG; SR 221.213.11) den bisherigen Mietzins sowie die bisherige Belastung des Mieters für Nebenkosten, den neuen Mietzins sowie die neue Belastung des Mieters für Nebenkosten, den Zeitpunkt, auf den die Erhöhung in Kraft tritt, und die klare Begründung der Erhöhung enthalten. Werden mehrere Erhöhungsgründe geltend gemacht, so sind diese je in Einzelbeträgen auszuweisen. Dass ein Formular inhaltlich den Anforderungen von <ref-law> entspricht, genügt nicht. Aus Gründen der Klarheit und einheitlichen Handhabung sowie der Rechtssicherheit ist notwendig, dass das Formular von der zuständigen kantonalen Instanz genehmigt wurde (<ref-ruling> E. 3b S. 217).
1.3 Eine Verletzung der Zuständigkeitsvorschriften, wie sie die Beschwerdeführer geltend machen, läge vor, wenn die kantonalen Gerichte das betreffende Formular selbst an Stelle der kantonalrechtlich hierfür vorgesehenen Behörde genehmigt hätten. Kommt demgegenüber der Richter im Rahmen eines Prozesses zum Ergebnis, das für die Erhöhung verwendete Formular sei von der zuständigen Behörde genehmigt worden, stellt er lediglich den im Prozess massgeblichen Sachverhalt fest. Ausserhalb des Prozesses kommt dieser Sachverhaltsfeststellung keine Bedeutung zu. Da der Richter keine Genehmigung des Formulars vornimmt, ist auch keine Verletzung der Zuständigkeitsordnung gegeben. Es stellt sich einzig die Frage, ob die Sachverhaltsfeststellung angesichts der anderslautenden Auskünfte der zuständigen Behörden korrekt erfolgte.
1.4 Auf Beschwerde in Zivilsachen hin kann das Bundesgericht zwar prüfen, ob eine Feststellung in tatsächlicher Hinsicht offensichtlich unrichtig und damit willkürlich ist (<ref-law>). Der Rechtsuchende hat indessen im einzelnen darzulegen, weshalb die Auffassung der Vorinstanz offensichtlich unhaltbar und damit willkürlich sein soll (<ref-ruling> E. 1.4.3 S. 254 f.; <ref-ruling> E. 2.4 S. 466 f.). Die Beschwerdeführer berufen sich auf die von den zuständigen Behörden erteilten Auskünfte und machen geltend, es sei von der urteilenden Instanz nicht nachzuprüfen, ob diese Auskunft richtig oder falsch sei. Zur Begründung einer Willkürrüge müssten die Beschwerdeführer aber darlegen, inwiefern die Annahme, die Auskünfte seien falsch, offensichtlich unhaltbar und damit willkürlich ist. Dazu genügen ihre Ausführungen nicht, so dass der angefochtene Entscheid insoweit nicht zu überprüfen ist.
1.5 Als aktenwidrig rügen die Beschwerdeführer die Feststellung der Vorinstanz, die Beschwerdegegnerin habe für die Mietzinserhöhung das genehmigte Formular verwendet. Nicht nur die grafische Gestaltung sei völlig unterschiedlich, auch die Firmierung sei eigenhändig abgeändert worden. Zudem sei der Hinweis "Formular genehmigt durch die zuständige Amtsstelle" beigefügt worden.
1.5.1 Der Vorinstanz ist nicht entgangen, dass die beiden Formulare nicht identisch sind, wies sie doch ausdrücklich auf die Firmenänderung hin. Die Vorinstanz ging vielmehr davon aus, die abweichende Gestaltung ändere nichts daran, dass es sich um ein genehmigtes Formular handle. Ob diese Annahme zutrifft, ist eine Rechtsfrage, welche das Bundesgericht unter dem Blickwinkel des Bundesrechts (mit Ausnahme der verfassungsmässigen Rechte der Beschwerdeführer) von Amtes wegen prüfen kann (<ref-law>). Soweit keine hinreichend begründeten Sachverhaltsrügen erhoben werden (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG), stützt sich das Bundesgericht dabei grundsätzlich aber auf die im angefochtenen Entscheid enthaltenen tatsächlichen Feststellungen (<ref-law>).
1.5.2 Soweit sich Abweichungen zwischen dem genehmigten und dem verwendeten Formular nicht bereits aus den tatsächlichen Feststellungen im angefochtenen Entscheid ergeben, müssten die Beschwerdeführer diesbezüglich substantiiert eine Ergänzung des Sachverhalts beantragen und danach ausführen, inwiefern die Annahme, das Formular habe trotz der Änderung als genehmigt zu gelten, Recht verletzt (<ref-law>). Diesen Anforderungen genügen die Vorbringen der Beschwerdeführer nicht. Ob eine Abänderung dazu führt, dass das geänderte Formular als nicht genehmigt anzusehen ist, kann nämlich nicht ohne Rücksicht auf die vorgenommenen Modifikationen und den mit dem Formularzwang verfolgten Zweck entschieden werden. So unterscheidet sich das verwendete vom genehmigten Formular beispielsweise darin, dass die Adresse der Mietschlichtungsstelle aktualisiert wurde. Es versteht sich von selbst, dass die korrekte Adressangabe vom Gesetz gewollt ist und der Nachvollzug der Adressänderung nicht dazu führt, dass erneut eine Genehmigung eingeholt werden müsste.
1.5.3 Auf die einzelnen Abweichungen braucht indessen nicht näher eingegangen zu werden, denn die Beschwerdegegnerin verweist auf zwei bei den Akten liegende genehmigte Formulare anderer Liegenschaftsverwaltungen, die mit Ausnahme der Geschäftsfirma und deren Logo mit dem von der Beschwerdegegnerin verwendeten Formular identisch sind. Die Beschwerdeführer berufen sich zwar auf ein im Kanton Luzern ergangenes Urteil (LGVE 1993 I Nr. 9 S. 10 ff.), gemäss welchem die Genehmigung privat kreierter Formulare personenbezogen zu erfolgen hat, damit der zuständigen Behörde bei Anfragen eine effiziente Kontrolle, ob ein Formular genehmigt wurde, ermöglicht wird. Diese liesse sich indessen besser erreichen, indem das Formular mit einer Identifikationsnummer versehen wird. Der Umfang des notwendig vorformulierten Formularinhalts wird abschliessend durch <ref-law> geregelt (HIGI, Zürcher Kommentar, 4. Aufl. 1998, N. 190 zu <ref-law> mit Hinweis). Aus <ref-law> ergibt sich, dass der Vermieter genehmigte Erhöhungsformulare beziehen können muss, was voraussetzt, dass unpersönliche Formulare zur Verfügung gestellt werden. Unterscheidet sich das verwendete Formular von einem genehmigten nur in der Firma und dem Kennzeichen des unterzeichnenden Unternehmens, betrifft die Abweichung den individuell auszufüllenden und nicht den allgemeingültigen und damit der Formalisierung überhaupt zugänglichen Teil des Formulars. Mit der Bezeichnung der Vermieterschaft oder der für diese handelnden Gesellschaft wird für den Mieter ersichtlich, wer das Formular verwendet. Dass der Mieter die notwendigen Informationen in der vom Kanton genehmigten Form erhält, bleibt garantiert, solange weder inhaltlich noch in der Darstellung weitere Änderungen vorgenommen werden. Damit ist dem Zweck von <ref-law>, dem Mieter den Rechtsweg aufzuzeigen und ihm eine möglichst einfache Beurteilung seiner Chancen zu sichern, die angekündigte Mietzinserhöhung anzufechten, Genüge getan und diesbezüglich die vom Gesetz gewollte vorgängige Kontrolle gewährleistet (<ref-ruling> E. 3b S. 217 mit Hinweisen). Aufgrund der Aktenlage ist somit erstellt, dass das verwendete Formular einem von der zuständigen Behörde genehmigten entspricht. Gegenüber wem und mit welchem Firmenlogo diese Genehmigung erfolgte, ist nicht massgebend.
2. Bezüglich des Quantitativs der Mietzinserhöhung akzeptieren die Beschwerdeführer vor Bundesgericht den für die geltend gemachten Investitionen angenommenen wertvermehrenden Anteil von 50 %. Sie bemängeln aber, die Vorinstanz sei gestützt auf eine Zusammenstellung der Beschwerdegegnerin von einem Sanierungsaufwand von Fr. 6'985'703.-- ausgegangen, obwohl entgegen dem ausdrücklichen Antrag der Beschwerdeführer vor erster Instanz (ebenso in der kantonalen Beschwerde S. 13) keinerlei Belege vorgelegen hätten.
2.1 Die Vorinstanz hielt fest, es sei unbestritten, dass die Beschwerdegegnerin im Jahr 2002 Arbeiten im Gegenwert von Fr. 6'985'703.-- habe vornehmen lassen. Trifft diese Feststellung zu, war die Vorinstanz nicht gehalten, Belege für den Sanierungsaufwand zu verlangen.
2.2 Die Beschwerdeführer geben diese Feststellung nicht explizit als willkürlich aus. Auch aus ihrem Hinweis auf ihre kantonale Beschwerdeschrift ergibt sich keine Bestreitung der Höhe der Investition der Beschwerdegegnerin für die Sanierung, erfolgten doch die Ausführungen an der angegebenen Stelle nicht zu den wertvermehrenden Investitionen, sondern unter dem Titel "Einrede des übersetzten Ertrages". Daher ist keineswegs unhaltbar, wenn die Vorinstanz den von der Beschwerdegegnerin angegebenen Sanierungsaufwand von Fr. 6'985'703.-- mit Bezug auf die Mietzinserhöhung zufolge wertvermehrender Investitionen als unbestritten betrachtete. Im Übrigen führen die Beschwerdeführer vor Bundesgericht (Beschwerde S. 9) selbst an, sie hätten in ihrer eigenen Berechnung den Sanierungsaufwand mit Fr. 6'985'703.-- als aufgeschobenen Unterhalt berücksichtigt.
3. Die Beschwerdeführer machen geltend, die bisherigen Anlagen und Einrichtungen hätten ein Alter von über 30 Jahren aufgewiesen. Daher sei für die neuen Investitionen zumindest eine gleich lange Lebensdauer einzusetzen. Zudem kritisieren sie, dass die Vorinstanz den Mehrwertanteil entsprechend der Quadratmeterzahl der Wohnungen auf die Mieter überwälzt hat. Sie begründen dies damit, dass die Renovation nur in Küche und Bad zu Verbesserungen geführt habe, weshalb die Überwälzung nach Massgabe der gesamten Wohnfläche nicht gerechtfertigt sei. Ausserdem sei auch die Gesamtfläche von 8534 Quadratmetern, welche die Beschwerdegegnerin ihrer Berechnung zugrunde gelegt habe, unbelegt. Ferner sei unklar geblieben, wie sich die Gesamtfläche auf die verschiedenen Wohnungstypen und Räumlichkeiten (Geschäftsräume, Büros, Garagen, Keller u.ä.) verteile.
3.1 Die Beschwerdeführer stützen ihre Vorbringen auf Sachverhaltselemente (wie beispielsweise das Alter der bisherigen Einrichtungen), die den tatsächlichen Feststellungen des angefochtenen Entscheides nicht zu entnehmen sind, ohne eine hinreichend begründete Rüge zu erheben, die dem Bundesgericht eine Ergänzung des Sachverhalts erlauben würde. Damit sind sie nicht zu hören. Welcher Verteilschlüssel im Einzelfall zur Anwendung kommt, ist mit Blick auf die konkreten tatsächlichen Verhältnisse zu entscheiden. Auch wenn nur gewisse Teile einer Wohnung renoviert werden, kann diese als Ganzes davon profitieren (vgl. SVIT-Kommentar, Das Schweizerische Mietrecht, 3. Aufl. 2008, N. 86 zu <ref-law>). Gestützt auf die tatsächlichen Feststellungen im angefochtenen Entscheid ist nicht ersichtlich, inwiefern die Aufteilung des Mehrwerts durch die Vorinstanz Bundesrecht verletzen sollte.
3.2 Soweit die Beschwerdeführer beanstanden, die Grundlagen der Berechnung seien von der Beschwerdegegnerin nicht hinreichend belegt, beziehungsweise offen gelegt worden, verweisen sie wiederum auf ihre kantonale Beschwerdeschrift (S. 10). Die Ausführungen an der angeführten Stelle erfolgten indessen ebenfalls zur "Einrede des übersetzten Ertrages" und nicht zu der Verteilung des Mehrwerts auf die einzelnen Wohnungen, so dass für die Vorinstanz kein Anlass bestand, diesbezüglich den detaillierten Nachweis der Berechnungsgrundlagen zu verlangen.
4. Die Beschwerdeführer sind der Auffassung, die Beschwerdegegnerin erziele einen übersetzten Ertrag. Es sei deren Sache, einen angemessenen Ertrag nachzuweisen.
4.1 Weist der Vermieter nach, dass sich die Mietzinserhöhung durch Mehrleistungen rechtfertigen lässt, ist sie in der Regel nicht missbräuchlich (<ref-law>). Macht der Mieter geltend, ausnahmsweise führe die Erhöhung dennoch zu einem übersetzten Ertrag, hat er den entsprechenden Beweis anzutreten (vgl. LACHAT UND ANDERE, Das Mietrecht für die Praxis, 8. Aufl. 2009, S. 438 f. Rz. 21/5.2.2 und 21/5.3.2; vgl. auch Urteil des Bundesgerichts 4C.323/2001 vom 9. April 2002, E. 3a, in: SJ 2002 I S. 434 ff.). Dies ist den Beschwerdeführern nach den Feststellungen der Vorinstanz nicht gelungen. Damit bleibt es bei der Zulässigkeit der nach der relativen Methode berechneten Mietzinserhöhung entsprechend den getätigten Investitionen. Eine Verletzung der Beweislastverteilung liegt nicht vor. Aus dem Urteil des Bundesgerichts 4C.236/2004 vom 12. November 2004, in: mp 2005 S. 86 ff., auf welches sich die Beschwerdeführer berufen, können sie nichts zu ihren Gunsten ableiten. Im zitierten Entscheid war - im Gegensatz zum vorliegenden Fall - der Nachweis einer übersetzten Nettorendite offensichtlich bereits erbracht, hielt doch das Bundesgericht der Vermieterschaft, die sich gegen eine der Mieterin zugestandene Herabsetzung des Mietzinses zur Wehr setzte, entgegen, auch für eine alte Liegenschaft sei eine Ertragsberechnung stets möglich, wenn das Kriterium der Quartierüblichkeit von der Gegenseite nicht angerufen werde (E. 3.3). Der Beschwerdegegnerin ist der Nachweis geglückt, dass sich die Anpassung des Mietzinses nach der relativen Methode rechtfertigen lässt. Die Beschwerdeführer haben demgegenüber den Nachweis, dass der erhöhte Mietzins nach der absoluten Methode (im Vergleich zum Quartierüblichen oder wegen übersetzter Nettorendite) missbräuchlich erscheint, nicht geleistet. Unter diesen Umständen ist die Beschwerdegegnerin nicht gehalten, zusätzlich die Angemessenheit der Nettorendite oder die Quartierüblichkeit des Mietzinses nachzuweisen. Auf die diesbezüglichen Ausführungen der Vorinstanz und der Beschwerdeführer ist daher nicht einzugehen.
4.2 Die Beschwerdeführer machen allerdings geltend, da der Zivilgerichtspräsident ihre Ertragsrechnung für untauglich hielt, hätten sie zumindest aufgefordert werden müssen, ihre Berechnung zu korrigieren. Auch unter der Geltung der sozialpolitisch begründeten Untersuchungsmaxime (<ref-law>) ist das Gericht indessen nicht verpflichtet, die Akten von sich aus zu durchforsten, um abzuklären, was sich daraus zu Gunsten der Partei, die das Beweismittel angerufen hat, herleiten liesse (Bundesgerichtsurteil 5C.134/2004 vom 1. Oktober 2004, E. 2.2 mit Hinweisen; HIGI, Zürcher Kommentar, 4. Aufl. 1996, N. 81 zu <ref-law>). Wenn die Vorinstanz die von den Beschwerdeführern als zulässig errechneten Mietzinse als unrealistisch tief einstufte, da diese den billigsten Mieten in Abbruchobjekten ohne jeden Komfort entsprachen, verletzt dies im Übrigen kein Bundesrecht.
4.3 Die Beschwerdeführer wenden ein, die Beschwerdegegnerin habe die zur Ertragsrechnung notwendigen Unterlagen nur teilweise ediert und ihre eigenen Zahlenangaben in keiner Weise belegt. Die Beschwerdeführer wollen daraus ableiten, tatsächlich werde ein übersetzter Ertrag erzielt. Sie zeigen aber nicht auf, dass und inwiefern fehlende Angaben der Beschwerdegegnerin dafür verantwortlich waren, dass die kantonalen Instanzen die von den Beschwerdeführern aufgestellte Ertragsrechnung für nicht stichhaltig hielten. War eine allenfalls unvollständige Information aber nicht entscheidrelevant, können die Beschwerdeführer daraus nichts zu ihren Gunsten ableiten.
5. Die Beschwerde erweist sich insgesamt als unbegründet und ist abzuweisen, soweit darauf einzutreten ist. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer kosten- und entschädigungspflichtig.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 1'500.-- werden mit Fr. 800.-- den Beschwerdeführern 1 und mit Fr. 700.-- der Beschwerdeführerin 2 auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit insgesamt Fr. 2'500.-- zu entschädigen, wobei auf die Beschwerdeführer 1 Fr. 1'400.-- und auf die Beschwerdeführerin 2 Fr. 1'100.-- entfallen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 10. Februar 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Luczak