Sachverhalt: A. Zwischen A._ und B._ (Beschwerdeführer; Mieter) und der X._-genossenschaft (Beschwerdegegnerin; Vermieterin) bestanden zwei Mietverhältnisse betreffend eine 3.5-Zimmerwohnung und eine 1-Zimmerwohnung in der Liegenschaft D._-strasse 18 in E._. Das Mietverhältnis über die 3.5-Zimmerwohnung dauerte vom 1. Januar 1997 bis am 30. November 2006. Das Mietverhältnis über die 1-Zimmerwohnung bestand ursprünglich zwischen der Beschwerdegegnerin und dem Vormieter C._ und ging mittels Vertragsüberschreibung per 1. April 2004 auf die Beschwerdeführer über. Es endete ebenfalls am 30. November 2006. Die monatliche Miete für die 3.5-Zimmerwohnung betrug Fr. 1'350.--, zuzüglich Heiz- und Nebenkosten von Fr. 150.-- als Akontozahlung. Die monatliche Miete der 1-Zimmerwohnung belief sich auf Fr. 200.--, zuzüglich Heiz- und Nebenkosten von Fr. 50.-- als Akontozahlung. B. Am 8. August 2007 belangten die Beschwerdeführer die Beschwerdegegnerin bei der kantonalen Schlichtungsstelle für Mietangelegenheiten auf Zahlung von Fr. 12'273.-- nebst Zins. Ausserdem begehrten sie die Edition der Nebenkostenabrechnungen für die Perioden 1. Januar 1997 bis 30. Juni 2004. Eine Einigung kam nicht zustande. Mit Klage vom 19. November 2007 beantragten die Beschwerdeführer dem Bezirksgericht Arlesheim, die Beschwerdegegnerin sei zur Zahlung von Fr. 34'640.15 nebst Zins zu 5 % ab 1. Oktober 2001 (aufgrund zu viel bezahlter Nebenkosten) und zur Edition der Nebenkostenabrechnungen für die 1-Zimmerwohnung für die Perioden 1. Januar 1997 bis 30. Juni 2004 zu verurteilen. Ausserdem habe die Beschwerdegegnerin das Anteilsscheinkapital von Fr. 5'000.-- herauszugeben. Später reduzierten die Beschwerdeführer ihre Forderung von Fr. 34'640.15 auf Fr. 28'456.10, wovon sie zudem einen der Beschwerdegegnerin zustehenden Betrag von Fr. 3'730.-- in Abzug brachten. Die Beschwerdegegnerin beantragte die Abweisung der Klage, soweit darauf einzutreten sei. Mit Urteil vom 27. Juni 2008 hiess der Gerichtspräsident des Bezirksgerichts Arlesheim die Klage teilweise gut und verurteilte die Beschwerdegegnerin, den Beschwerdeführern Fr. 6'186.-- nebst Zins zu 5 % seit 19. November 2007 zu entrichten und ihnen das Anteilsscheinkapital von Fr. 5'000.-- zurückzubezahlen. Gegen dieses Urteil appellierten die Beschwerdeführer an das Kantonsgericht Basel-Landschaft, Abteilung Zivil- und Strafrecht. Sie beantragten, die Beschwerdegegnerin zur Zahlung von Fr. 24'726.10 nebst Zins zu 5 % ab dem 19. November 2007 und zur Rückzahlung des Anteilsscheinkapitals von Fr. 5'000.-- zu verpflichten. In der Appellationsbegründung reduzierten die Beschwerdeführer ihre Forderung auf Fr. 23'046.10 nebst Zins zu 5 % ab 19. November 2007. Die Beschwerdegegnerin erhob Anschlussappellation. Sie verlangte die vollumfängliche Abweisung der Klage, soweit sie von den Beschwerdeführern noch aufrecht erhalten werde und darauf überhaupt eingetreten werden könne. Mit Urteil vom 20. Januar 2009 hob das Kantonsgericht - in Abweisung der Appellation, soweit es auf diese eintrat, und in Gutheissung der Anschlussappellation - das Urteil des Bezirksgerichtspräsidiums auf und wies die Klage ab. C. Die Beschwerdeführer beantragen mit Beschwerde in Zivilsachen, das Urteil des Kantonsgerichts aufzuheben und die Beschwerdegegnerin zur Zahlung von Fr. 23'046.10 nebst Zins zu 5 % ab 19. November 2007 zu verurteilen. Die Beschwerdegegnerin habe ihnen zudem das Anteilsscheinkapital von Fr. 1'000.-- zurückzubezahlen. Eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Beim im Rechtsbegehren genannten Betrag von Fr. 1'000.-- dürfte es sich um einen Verschrieb handeln, da sonst überall - namentlich auch in der Beschwerdebegründung - von einem Anteilsscheinkapital von Fr. 5'000.-- die Rede ist. Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne, und das angefochtene Urteil zu bestätigen. Die Vorinstanz schliesst, unter Hinweis auf die Begründung des angefochtenen Urteils, auf Abweisung der Beschwerde.