Sachverhalt: Sachverhalt: A. X._ und Y._ (Beschwerdeführer, Mieter) sind seit 1. April 2000 Mieter einer 4 1/2-Zimmerwohnung an der Strasse A._ in Basel. Der Mietvertrag vom 31. Januar/3. Februar 2000 verpflichtet die Mieter in Ziffer 4 unter dem Titel "Mietzins, Nebenkosten und Zahlungstermine" zur Zahlung von monatlich Fr. 260.-- "à Kto. Betriebskosten". In Ziffer 6 unter dem Titel "Allgemeine Bestimmungen" erklärt der individuelle Mietvertrag die "Allgemeinen Vertragsbestimmungen zum Mietvertrag für Wohnungen" (AVB) zu seinem integrierenden Bestandteil. Die dem individuellen Vertrag beigefügten AVB enthalten eine Ziffer 21 mit dem Titel "Heiz- und Betriebskosten, Fixkosten". Deren Unterziffer 21.7 lautet: "Als Heizkosten gelten die Aufwendungen zur Wärmeerzeugung, insbesondere das Heizmaterial (Erdöl, Strom, Gas, feste Brennstoffe usw.); die Reinigung und Wartung der Heizanlage; die Kosten für die Lagerung des Brennmaterials; Service-abonnemente für Tank, Brenner und Pumpen; Stromkosten für Brenner und Pumpen." Die Unterziffer 21.8 lautet: "Zu den Betriebskosten gehören die Aufwendungen zu Betrieb und zu Pflege der Allgemeinen Teile, insbesondere die Kosten für: den Hauswartdienst, die entsprechenden Sozialleistungen und das Reinigungsmaterial; Allgemeinstrom und -wasser, Liftstrom; die Entkalkung von Boilern und Leitungsnetzen; Wasseraufbereitungssalz, -filter und -serviceabonnement; Serviceabonnemente von Aufzügen, Wasch-, Geschirrspül- und Trocknungsautomaten; Wasser-, Klär- und Kehrichtgebühren; Gebühren und Abonnementskosten sowie Urheberrechtsgebühren der Kabelnetzbetreiber, Gartenunterhalt." Ausser der Tätigung von Akontozahlungen beglichen die Mieter die Saldi von zwei Nebenkostenabrechnungen für die Jahre 2000/2002 sowie 2002/2003, die sie in den Jahren 2002 und 2003 erhalten hatten. Den Saldo einer dritten Abrechnung vom 15. Februar 2005 für die Monate Juli 2003 bis Juni 2004 bezahlten sie nicht mehr. Sie stellten sich nach Erhalt dieser Abrechnung auf den Standpunkt, die Nebenkosten seien ihnen mit der im Mietvertrag getroffenen Regelung nicht gültig überbunden worden und daher nicht geschuldet gewesen. Die von ihnen geleisteten Zahlungen seien im Irrtum über ihre Schuldpflicht erfolgt. Die Mieter verlangen von der Vermieterin, der Z._ (Beschwerdegegnerin, Vermieterin), die Rückerstattung der Zahlungen für Nebenkosten. B. Nachdem vor der staatlichen Schlichtungsstelle für Mietstreitigkeiten keine Einigung erzielt werden konnte, gelangten die Mieter an das Zivilgericht Basel-Stadt, Dreiergericht. Sie beantragten, die Vermieterin zur Bezahlung von Fr. 14'117.60 nebst Zins zu 5 % seit dem 29. April 2005 zu verpflichten. Das Dreiergericht wies die Klage am 14. Februar 2006 ab. Eine gegen diesen Entscheid gerichtete Beschwerde der Mieter wies das Appellationsgericht des Kantons Basel-Stadt, Ausschuss, am 17. August 2006 ab. Eine gegen diesen Entscheid gerichtete Beschwerde der Mieter wies das Appellationsgericht des Kantons Basel-Stadt, Ausschuss, am 17. August 2006 ab. C. Die Mieter beantragen mit staatsrechtlicher Beschwerde, das Urteil des Appellationsgerichts vom 17. August 2006 wegen Verletzung des Willkürverbots (Art. 9 BV) aufzuheben. Die Beschwerdegegnerin stellt den Antrag, auf die Beschwerde sei nicht einzutreten, eventuell sei sie abzuweisen. Die Beschwerdegegnerin stellt den Antrag, auf die Beschwerde sei nicht einzutreten, eventuell sei sie abzuweisen. D. Parallel zur Beschwerde haben die Beschwerdeführer in gleicher Sache eidgenössische Berufung eingelegt. 