Sachverhalt:
A. A._ (Beschwerdeführer) ist seit dem 1. Dezember 1997 Mieter einer 4 1⁄2-Zimmerwohnung an der C._-strasse 32 in Basel. Vermieterin ist die B._ (Beschwerdegegnerin).
B. Der Beschwerdeführer gelangte am 24. Juli 2007 mit dem Begehren an die Staatliche Schlichtungsstelle für Mietstreitigkeiten des Kantons Basel-Stadt, es sei festzustellen, dass die Warmwasserkosten und die Kosten für den Hauswart im Nettomietzins inbegriffen seien und nicht separat geschuldet würden. Weiter verlangte er die Rückerstattung zu Unrecht bezahlter Nebenkosten im Umfang von Fr. 7'781.65 nebst Zins zu 5 % ab Klageeinreichung. Nachdem vor der Schlichtungsstelle keine Einigung erzielt werden konnte, gelangte der Beschwerdeführer mit einer auf das Feststellungsbegehren bezüglich der Warmwasserkosten beschränkten Klage an das Dreiergericht des Zivilgerichts Basel-Stadt, welches die Klage mit Urteil vom 8. Juli 2008 abwies. Die vom Beschwerdeführer dagegen beim Appellationsgericht des Kantons Basel-Stadt eingereichte Beschwerde wurde mit Urteil vom 12. März 2009 abgewiesen.
C. Der Beschwerdeführer beantragt mit subsidiärer Verfassungsbeschwerde, das angefochtene Urteil sei aufzuheben.
Die Beschwerdegegnerin beantragt, auf die Beschwerde nicht einzutreten, eventualiter sei sie vollumfänglich abzuweisen. Die Vorinstanz schliesst auf Abweisung der Beschwerde.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1).
1.1 Die Beschwerdeschrift hat ein Rechtsbegehren zu enthalten (<ref-law>). Im Gegensatz zur altrechtlichen staatsrechtlichen Beschwerde, die grundsätzlich rein kassatorischer Natur war (vgl. etwa <ref-ruling> E. 1.2.1 S. 131 f.), ist die subsidiäre Verfassungsbeschwerde (gleich wie die ordentliche Beschwerde) ein reformatorisches Rechtsmittel (<ref-law> in Verbindung mit <ref-law>). Daher darf sich der Beschwerdeführer grundsätzlich nicht darauf beschränken, die Aufhebung des angefochtenen Entscheids zu beantragen, sondern muss einen Antrag in der Sache stellen. Anträge auf Rückweisung der Sache an die Vorinstanz zu neuer Entscheidung oder blosse Aufhebungsanträge genügen nicht und machen die Beschwerde unzulässig. Ein blosser Rückweisungsantrag reicht ausnahmsweise aus, wenn das Bundesgericht im Falle der Gutheissung in der Sache nicht selbst entscheiden könnte, weil die erforderlichen Sachverhaltsfeststellungen der Vorinstanz fehlen (<ref-ruling> E. 1.3 S. 383 mit Hinweis).
1.2 Vorliegend beantragt der Beschwerdeführer lediglich, das angefochtene Urteil sei aufzuheben. Einen materiellen Antrag stellt er nicht, ebenso wenig einen Rückweisungsantrag. Ohnehin geht aus dem angefochtenen Entscheid nicht ohne weiteres hervor und wird auch in der Beschwerde in keiner Weise dargetan, dass das Bundesgericht im Falle der Gutheissung der Beschwerde nicht selbst in der Lage wäre, ein Urteil zu fällen und die Streitsache an die Vorinstanz zurückweisen müsste.
Demnach ergibt sich, dass der Beschwerdeführer keinen rechtsgenüglichen Antrag gestellt hat und demzufolge auf die Beschwerde nicht eingetreten werden kann.
2. Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
2. Die Gerichtskosten von Fr. 500.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 5. Oktober 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Die Gerichtsschreiberin:
Klett Sommer