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.