Sachverhalt:
A. Die von A._ beherrschte Y._ GmbH (Beschwerdegegnerin) vermittelte für die FC X._ AG und später für den Fussballclub X._ (Beschwerdeführer) Sponsoren auf Provisionsbasis. Anfangs 2004 befand sich die FC X._ AG in finanziellen Schwierigkeiten. Unter anderem schuldete sie der Beschwerdegegnerin Provisionen im Betrag von etwa Fr. 240'000.--. Am 12. Januar 2004 übergab B._, der damalige Verwaltungsratspräsident der FC X._ AG, A._ einen WIR-Check über nominal Fr. 110'000.-- zu einem anrechenbaren Wert von Fr. 66'000.-- (60%). Der Beschwerdeführer behauptet, die FC X._ AG habe mit A._ abgemacht, dass die Beschwerdegegnerin mit dem Geld ausstehende Sozialversicherungsbeiträge der FC X._ AG in der Höhe von Fr. 28'763.-- begleiche und den Rest (Fr. 37'237.--) an ihre offenen Provisionsforderungen anrechne. Die Beschwerdegegnerin bestreitet, dass sie sich zur Begleichung der Sozialversicherungsbeiträge verpflichtet habe.
Am 24. März 2004 wurde der FC X._ AG die provisorische Nachlassstundung bewilligt. Am 4. Mai 2004 veräusserte die FC X._ AG in prov. Nachlassstundung ihre Aktiven und übertrug den Spielbetrieb auf den Beschwerdeführer. Im Rahmen dieser Vereinbarung bezahlte der Beschwerdeführer der FC X._ AG ausserdem einen Barbetrag zur Tilgung privilegierter Schulden, darunter die betreffenden Sozialversicherungsbeiträge. Im Gegenzug trat die FC X._ AG dem Beschwerdeführer u.a. eine allfällige Forderung gegenüber der Beschwerdegegnerin ab. Gemäss dem am 13. Dezember 2004 genehmigten Nachlassvertrag erhielt die Beschwerdegegnerin auf ihre Forderung von Fr. 153'380.-- eine Nachlassdividende von Fr. 4'601.40.
B. Am 26. Juni 2007 beantragte der Beschwerdeführer dem Kreisgericht Untertoggenburg-Gossau, die Beschwerdegegnerin sei zu verpflichten, ihm den Betrag von Fr. 28'763 nebst Zins zu 5% seit 1. Juli 2004 zuzüglich Betreibungskosten von Fr. 300.-- anzuerkennen und zu bezahlen. Mit Entscheid vom 22. April 2008 wies das Kreisgericht die Klage ab.
Gegen diesen Entscheid gelangte der Beschwerdeführer an das Kantonsgericht St. Gallen, das die Berufung mit Entscheid vom 11. März 2009 abwies.
C. Der Beschwerdeführer beantragt mit subsidiärer Verfassungsbeschwerde, das Urteil des Kantonsgerichts vom 11. März 2009 aufzuheben und die Sache zur neuen Beurteilung/Entscheidung an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen. Die Vorinstanz verzichtete auf eine Vernehmlassung.

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 Beschwerde in Zivilsachen) 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. Er muss demnach angeben, welche Punkte des Entscheids angefochten und welche Abänderungen beantragt werden. 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; <ref-ruling> E. 3.1).
Vorliegend verlangt der Beschwerdeführer lediglich, der Entscheid des Kantonsgerichts vom 11. März 2009 sei aufzuheben und die Sache zur neuen Beurteilung/Entscheidung an die Vorinstanz zurückzuweisen. Einen materiellen Antrag stellt er nicht. 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, geht aus dem angefochtenen Entscheid nicht ohne weiteres hervor und wird auch in der Beschwerde in keiner Weise dargetan, wird doch nicht begründet, weshalb die Streitsache zur neuen Beurteilung an die Vorinstanz zurückzuweisen sei.
Demnach ergibt sich, dass der Beschwerdeführer keinen rechtsgenüglichen Antrag gestellt hat und demzufolge auf die Beschwerde nicht eingetreten werden kann.
1.2 Beizufügen ist, dass auf die Beschwerde auch deshalb nicht eingetreten werden kann, weil sich der Beschwerdeführer darauf beschränkt, die Beweiswürdigung im angefochtenen Entscheid in appellatorischer Weise zu kritisieren (<ref-ruling> E. 2.1; <ref-ruling> E. 3.1 S. 399), wobei er den von der Vorinstanz verbindlich festgestellten Sachverhalt nach Belieben ergänzt, ohne zu substanziieren, inwiefern er Ausnahmen von der Sachverhaltsbindung gemäss <ref-law> beanspruchen können soll (vgl. dazu <ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3, 393 E. 7.1, 462 E. 2.4; <ref-ruling> E. 6.2). Soweit in einer Beschwerde, wie vorliegend, Willkür in der Ermittlung des Sachverhalts geltend gemacht wird, ist zu beachten, dass dem Sachrichter in der Beweiswürdigung ein breiter Ermessensspielraum zusteht; der Beschwerdeführer hat daher darzulegen, inwiefern das kantonale Gericht sein Ermessen missbraucht, insbesondere offensichtlich unhaltbare Schlüsse gezogen, erhebliche Beweise übersehen oder willkürlich ausser Acht gelassen habe (Art. 106 Abs. 2 in Verbindung mit <ref-law>; vgl. BGE <ref-ruling> E. 3.2; <ref-ruling> E. 2.1; <ref-ruling> E. 2.1; <ref-ruling> E. 4b S. 40; <ref-ruling> E. 1b S. 30). Diesen Begründungsanforderungen vermag der Beschwerdeführer nicht zu genügen, woran auch nichts ändert, dass er im Anschluss an seine appellatorischen Vorbringen jeweils behauptet, der angefochtene Entscheid sei willkürlich.
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. 1'000.-- 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 Kantonsgericht St. Gallen, III. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 9. Juli 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Widmer