Sachverhalt:
A. Die X._ AG (Beschwerdegegnerin) bietet unter anderem Kurse für die Ausbildung von Fahrlehrern im Motorfahrzeugbereich an. Anfangs 2006 meldete sich A._ (Beschwerdeführer) für den Kurs "Fahrlehrer-Ausbildung Auto Kat. I intensiv" an. Mit Schreiben vom 27. April 2006 bestätigte die Beschwerdegegnerin die Anmeldung definitiv und liess ihm zwei Rechnungen sowie ihre Geschäftsbedingungen zukommen. Der Kurs begann am 17. Juli 2006 und sollte bis zum 12. Dezember 2006 dauern. Die Kosten beliefen sich auf insgesamt Fr. 16'900.--. Am 10. Mai 2006 bezahlte der Beschwerdeführer eine Anzahlung von Fr. 900.-- und am 4. Juli 2006 als erste Rate den Betrag von Fr. 8'000.--. Nachdem der Beschwerdeführer den Ausbildungslehrgang vereinbarungsgemäss angetreten hatte, brach er den Kursbesuch am 30. August 2006 "aus persönlichen Gründen" ab.
Die Beschwerdegegnerin stellte ihm am 9. Oktober 2006 das restliche Schulgeld von Fr. 8'000.-- in Rechnung. Dieser Zahlungsaufforderung und einer Mahnung vom 6. Dezember 2006 kam der Beschwerdeführer nicht nach.
B. Am 29. Mai 2007 leitete die Beschwerdegegnerin beim Bezirksgericht Zürich gegen den Beschwerdeführer Klage ein, mit dem Begehren, diesen zu verpflichten, ihr Fr. 8'000.-- zuzüglich Zins von 5 % seit 1. Januar 2007 zu bezahlen. Sie stützte ihre Klage auf Ziffer 3 ihrer Geschäftsbedingungen, die Bestandteil des Vertrages mit dem Beschwerdeführer seien, wonach bei einem Austritt eines Fahrlehrerkandidaten aus der Schule ohne wichtigen Grund das ganze Schulgeld zu bezahlen sei. Anlässlich der Hauptverhandlung erhob der Beschwerdeführer Widerklage, mit der er die Rückzahlung der bereits erbrachten Leistungen von Fr. 8'900.-- nebst 5 % Verzugszins seit 12. Februar 2007 verlangte. Er stellte sich auf den Standpunkt, die von der Beschwerdegegnerin angerufene Bestimmung der Allgemeinen Geschäftsbedingungen sei unzulässig, da das Widerrufsrecht im Sinne von <ref-law> für auftragsrechtliche Verträge zwingend sei. Er habe jederzeit vom Vertrag zurücktreten können und sei infolge Hinfälligkeit des Honoraranspruchs nicht verpflichtet, das restliche Schulgeld zu bezahlen. Zudem könne er das bereits Geleistete zurückverlangen. Der Einzelrichter des Bezirks Zürich hiess am 10. Dezember 2007 die Klage gut und wies die Widerklage ab.
Gegen diesen Entscheid gelangte der Beschwerdeführer mit kantonaler Berufung an das Obergericht des Kantons Zürich. Er beantragte, das Urteil des Bezirksgerichts vom 10. Dezember 2007 aufzuheben, die Klage der Beschwerdegegnerin abzuweisen sowie seine Widerklage gutzuheissen. Eventuell sei die Sache zur Durchführung eines Beweisverfahrens an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin begehrte die Abweisung der Berufung. Mit Urteil vom 11. August 2008 schützte das Obergericht den Entscheid der ersten Instanz und verpflichtete den Beschwerdeführer, der Beschwerdegegnerin Fr. 8'000.-- zuzüglich 5 % Verzugszins seit dem 1. Januar 2007 zu bezahlen. Die Widerklage wies es ab. Wie der Einzelrichter ging das Obergericht von einer grundsätzlichen Anwendbarkeit der auftragsrechtlichen Normen aus und erachtete das jederzeitige Widerrufsrecht im Sinne von <ref-law> als nicht zwingend, da es sich beim Vertrag der Parteien um einen atypischen Auftrag handle. Die Parteien hätten daher mit der vereinbarten Kündigungsregelung in den Allgemeinen Geschäftsbedingungen davon abweichen können.
C. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen die Aufhebung des Urteils des Obergerichts vom 11. August 2008. Die Klage über den Betrag von Fr. 8'000.-- zuzüglich Zins sei abzuweisen und die Widerklage über Fr. 8'900.-- zuzüglich Zins sei gutzuheissen. Eventuell sei die Sache zur Beurteilung eines Ersatzanspruchs der Beschwerdegegnerin infolge Widerrufs des Auftragsverhältnisses zur Unzeit an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin begehrt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Obergericht verzichtet auf eine Vernehmlassung.
D. Mit Präsidialverfügung vom 29. September 2008 wurde das Gesuch des Beschwerdeführers um aufschiebende Wirkung abgewiesen.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1 S. 117, 379 E. 1 S. 381).
1.1 In vermögensrechtlichen Angelegenheiten ist die Beschwerde in Zivilsachen grundsätzlich nur gegeben, wenn der Streitwert mindestens Fr. 30'000.-- beträgt (<ref-law>). Da vorliegend weder die Hauptklage noch die Widerklage die Streitwertgrenze von Fr. 30'000.-- erreicht (<ref-law>), ist zu prüfen, ob sich eine Rechtsfrage von grundsätzlicher Bedeutung stellt und die Beschwerde daher dennoch zulässig ist (<ref-law>).
1.2 Der Begriff der Rechtsfrage von grundsätzlicher Bedeutung ist sehr restriktiv auszulegen. Soweit es bei der aufgeworfenen Frage lediglich um die Anwendung von Grundsätzen der Rechtsprechung auf einen konkreten Fall geht, handelt es sich nicht um eine Rechtsfrage von grundsätzlicher Bedeutung (<ref-ruling> E. 1.2 S. 117; <ref-ruling> E. 1.1 und 1.2 S. 495 f.). Die Voraussetzung von <ref-law> ist hingegen erfüllt, wenn ein allgemeines Interesse besteht, dass eine umstrittene Frage höchstrichterlich geklärt wird, um eine einheitliche Anwendung und Auslegung des Bundesrechts herbeizuführen und damit Rechtssicherheit herzustellen (<ref-ruling> E. 2.4 S. 648 f.). Eine neue Rechtsfrage kann vom Bundesgericht sodann beurteilt werden, wenn dessen Entscheid für die Praxis wegleitend sein kann, namentlich wenn von unteren Instanzen viele gleichartige Fälle zu beurteilen sein werden (Urteil 4A_299/2008 vom 28. Oktober 2008 E. 1.3 mit Hinweis, zur Publikation vorgesehen). Die neue Rechtsfrage muss aber von ihrem Gewicht her von grundlegender Bedeutung sein (Urteil 2C_116/2007 vom 10. Oktober 2007 E. 4.2). Auch eine vom Bundesgericht bereits entschiedene Rechtsfrage kann unter der Voraussetzung von grundsätzlicher Bedeutung sein, dass sich die erneute Überprüfung aufdrängt. Dies kann zutreffen, wenn die Rechtsprechung nicht einheitlich oder in der massgebenden Lehre auf erhebliche Kritik gestossen ist (<ref-ruling> E. 1.5 S. 357 f.) oder wenn in der Zwischenzeit neue Gesetzesbestimmungen in Kraft getreten sind (<ref-ruling> E. 1.2 S. 117). Zu berücksichtigen ist weiter, ob die Streitwertgrenze im Zusammenhang mit der umstrittenen Rechtsfrage überhaupt je erreicht werden kann (<ref-ruling> E. 1.2 S. 117 f., 267 E. 1.2.3 S. 271). In der Beschwerdeschrift ist gemäss <ref-law> auszuführen, inwiefern eine Frage von grundsätzlicher Bedeutung vorliegt (<ref-ruling> E. 2.2.2.1 S. 442, 645 E. 2.4 S. 648).
1.3 Der Beschwerdeführer bringt vor, die Vorinstanz wie auch die Parteien seien übereinstimmend davon ausgegangen, das vorliegende Rechtsverhältnis als Unterrichtsvertrag zu qualifizieren und auf dessen Auflösung Auftragsrecht (<ref-law>) anzuwenden. Das Vorliegen einer Rechtsfrage von grundsätzlicher Bedeutung begründet er damit, dass eine erhebliche Rechtsunsicherheit bezüglich der Frage bestehe, ob das jederzeitige Widerrufsrecht gemäss <ref-law> im Bereich der Unterrichtsverhältnisse wegbedungen werden könne.
1.4 Nach ständiger Rechtsprechung des Bundesgerichts ist das jederzeitige Auflösungsrecht gemäss <ref-law> zwingender Natur und darf vertraglich weder wegbedungen noch eingeschränkt werden. Das Bundesgericht bestätigte diese Rechtsprechung in <ref-ruling> E. 2 ausdrücklich. Seit diesem Entscheid hat es stets klar und unmissverständlich an der zwingenden Natur von <ref-law> festgehalten (vgl. Urteile 4C.373/2006 vom 29. Januar 2007 E. 4.3; 4P.155/2004 vom 4. Oktober 2004 E. 2.2.7; 4C.43/2003 vom 24. April 2003 E. 2.1; 4C.464/1997 vom 25. August 1998 E. 6b; 4C.443/1996 vom 26. März 1997 E. 1a; 4C.342/1996 vom 3. März 1997 E. 4d; 4C.79/1994 vom 2. August 1994 E. 2a; 4C.479/1993 vom 17. Mai 1994 E. 4a; 4C.212/1991 vom 25. Februar 1992 E. 3b/bb). Dies ergibt sich auch aus dem von der Vorinstanz zitierten Urteil 4C.447/2004 vom 31. März 2005. Entgegen der Auffassung der Vorinstanz hat das Bundesgericht in der Erwägung 5.4 dieses Entscheides die Frage, ob das zwingende Widerrufsrecht auch auf Verträge Anwendung finde, die nicht durch ein Vertrauensverhältnis dominiert sind, nicht offengelassen, sondern lediglich darauf hingewiesen, dass die entsprechende Frage in casu sowieso unerheblich sei, weil ein Vertrauensverhältnis vorliege.
1.5 Die Praxis des Bundesgerichts, wonach das jederzeitige Widerrufsrecht nach <ref-law> zwingender Natur ist, wird in der Lehre kritisiert und bleibt - wie im vorliegenden Fall - von den kantonalen Gerichten teilweise sogar unangewendet. In der Lehre sind die Meinungen zur Rechtsnatur von <ref-law> jedoch geteilt. Jedenfalls lässt sich keine herrschende Lehre eruieren. So ist ein Teil der Lehre der Auffassung, <ref-law> habe nur für typische Auftragsverhältnisse zwingenden Charakter, wobei "typisch" unterschiedlich definiert wird (vgl. BUCHER, Obligationenrecht, Besonderer Teil, 3. Aufl. 1988, S. 228; ENGEL, Contrats de droit suisse, 2. Aufl. 2000, S. 510; GEHRER/GIGER, in: Handkommentar zum Schweizer Privatrecht, 2007, N. 8 zu <ref-law>; HOMBURGER, Anmerkung zu <ref-ruling>, SZW 1991, S. 35 f.; HUGUENIN, Obligationenrecht, Besonderer Teil, 2. Aufl. 2004, N. 835; SCHNYDER, Das Schweizerische Obligationenrecht, 9. Aufl. 2000, S. 556 f.; WEBER, in: Basler Kommentar, 4. Aufl. 2007, N. 10 zu <ref-law>). Andere Lehrmeinungen gehen noch weiter, indem sie die zwingende Natur von <ref-law> grundsätzlich verneinen und das jederzeitige Widerrufsrecht - jedenfalls für entgeltliche Aufträge - als dispositiv qualifizieren (vgl. BÜHLER, in: Zürcher Kommentar, 3. Aufl. 1998, N. 63 zu <ref-law>; FELLMANN, in: Berner Kommentar, 4. Aufl. 1992, N. 132 f. zu <ref-law>; FRICK, Die Beendigung des einfachen Auftrages [Art. 404 und 405 OR], Diss. Basel 2005, S. 91; GAUCH, <ref-law> - Sein Inhalt, seine Rechtfertigung und die Frage seines zwingenden Charakters, recht 1992, S. 9 ff., 18 ff.; GAUCH, Der Auftrag, der Dauervertrag und <ref-law>, SJZ 2005, S. 520 ff., 524; HONSELL, Schweizerisches Obligationenrecht, Besonderer Teil, 8. Aufl. 2006, S. 324 ff.; MARKUS REBER, <ref-law> - ein erratischer Block aus dem Römischen Recht im heutigen Auftragsrecht, Thesen zur Kündigung des einfachen Auftrags, in: Festschrift für Bruno Huwiler zum 65. Geburtstag, 2007, S. 499 ff., 538, 544 f.). Auch findet sich der Vorschlag, zwischen Kündigungsmacht und Kündigungsrecht zu unterscheiden. So hält WERRO dafür, dass beide Vertragsparteien jederzeit und ungeachtet vertraglicher Bindungen die Macht haben, den Auftrag zu beenden, hingegen das Recht dazu durch vertragliche Absprachen einschränkbar sei (WERRO, La distinction entre le pouvoir et le droit de résilier: la clé de l'interprétation de l'art. 404 CO, BR 1991, S. 55 ff.; WERRO, Le mandat et ses effets, 1993, S. 96 ff.).
1.6 Wie in der Erwägung 1.2 vorhergehend ausgeführt, kann sich eine erneute Überprüfung einer vom Bundesgericht bereits entschiedenen Rechtsfrage aufdrängen, wenn die Rechtsprechung in der massgebenden Lehre auf erhebliche Kritik gestossen ist. Vorliegend drängt sich eine Überprüfung der seit Jahrzehnten konstanten Praxis des Bundesgerichts indessen gerade nicht auf. Die Frage der Rechtsnatur von <ref-law> ist seit dem Grundsatzentscheid <ref-ruling> mehrfach aufgeworfen und eine erneute Überprüfung in Kenntnis der abweichenden Lehrmeinungen stets als entbehrlich betrachtet worden. Das Bundesgericht hat bisher an seiner Praxis festgehalten und insbesondere erwogen, dass diese Praxis zwar kritisiert wird, sich die Kritiker aber keineswegs darüber einig sind, wie eine geänderte Praxis aussehen müsste (vgl. Urteil 4C.443/1996 vom 26. März 1997 E. 1a). Daran hat sich nichts geändert. Auch heute gibt es - entgegen der Ansicht der Vorinstanz - keine herrschende Lehre (vgl. Erwägung 1.5). Demzufolge besteht kein Bedürfnis zur Überprüfung der klaren und konstanten Rechtsprechung zur zwingenden Natur von <ref-law>. Eine Rechtsfrage von grundsätzlicher Bedeutung im Sinne von <ref-law> ist somit zu verneinen, womit ein Eintreten auf die Beschwerde gestützt auf <ref-law> entfällt.
1.7 Da der Beschwerdeführer keine Verletzung verfassungsmässiger Rechte rügt und insbesondere nicht geltend macht, der angefochtene Entscheid sei willkürlich, kann die Beschwerde auch nicht als Verfassungsbeschwerde (<ref-law>) entgegengenommen werden.
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 Beschwerde 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 Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 10. Februar 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Die Gerichtsschreiberin:
Klett Sommer