Sachverhalt:
A. R._ (Kläger, Beschwerdeführer) schloss am 26. März 1994, gesetzlich vertreten durch seinen Vater, mit der Rechtsvorgängerin der X._ AG (Beklagte, Beschwerdegegnerin) eine sogenannte "Heiratsversicherung" über Fr. 100'000.-- ab.
Es handelt sich dabei um eine gemischte Lebensversicherung (Erlebnisfall-Kapital und Todesfallrisiko) als Hauptversicherung, kombiniert mit einer Heiratszusatzversicherung. Dabei wird die Erlebnisfall-Summe vorzeitig ausbezahlt, falls das versicherte Kind vor Ablauf der Versicherungsdauer heiratet. Der Vertragsbeginn war auf den 3. September 1994, das Vertragsende auf den 3. September 2010 festgesetzt. Die Erstprämie war am 3. September 1994 und die Folgeprämien jeweils auf den 1. September fällig.
Nach Darstellung des Klägers heiratete er am 1. August 2004 und liess der Beklagten in der Folge das notariell beglaubigte und übersetzte Heiratszertifikat sowie die Identitätspapiere der Eheleute zukommen. Die Beklagte verweigerte die Auszahlung der Versicherungssumme mit der Begründung, es bestehe ein begründeter Verdacht auf eine Fälschung des ihr eingereichten "Original Marriage Certificate". Die Beklagte trat daraufhin am 17. Januar 2005 gestützt auf <ref-law> vom Versicherungsvertrag zurück und bezahlte dem Kläger am 5. April 2005 den Rückkaufswert der Versicherungspolice in Höhe von Fr. 58'911.--.
Der Kläger stellte sich auf den Standpunkt, er habe Anspruch auf die gesamte Versicherungssumme von Fr. 100'000.--, da er seine Heirat genügend belegt habe; er bestand daher auf der Zahlung des Differenzbetrags (d.h. Fr. 41'089.--) zur bereits ausbezahlten Summe. Darüber hinaus forderte er von der Beklagten die für das Jahr 2004 zu viel bezahlte Restprämie von Fr. 590.60 (entsprechend einem Zwölftel der Jahresprämie von Fr. 7'087.40).
Zur Zahlung der Prämien halten die Allgemeinen Versicherungsbedingungen (AVB) in Ziffer 27 Folgendes fest:
"27.1 Die erste Prämie ist am Tag des Vertragsbeginns fällig; die folgenden Prämien verfallen am ersten Tag des Monats, mit dem die Versicherungsperiode beginnt, auf welche sie sich beziehen. Sie sind innert dreissig Tagen seit ihrem Verfall zahlbar.
27.2 ...
27.3 Die [Beklagte] erstattet dem aus der Versicherung Begünstigten denjenigen Teil der periodischen Prämien zurück, der am Ende des Versicherungsmonats, in dessen Verlauf der Versicherte gestorben ist, noch nicht verbraucht ist."
B. B.a R._ klagte am 4. April 2007 beim Bezirksgericht Zürich gegen die X._ AG auf Zahlung von Fr. 41'679.60 zuzüglich Zins zu 5 % seit 12. Oktober 2004. Das Bezirksgericht hiess die Klage im Umfang von Fr. 41'089.-- gut; im Restbetrag wies es die Klage ab.
B.b Der Kläger erhob beim Obergericht des Kantons Zürich Berufung und beantragte bezüglich der Abweisung der Klage im Mehrbetrag von Fr. 590.60 die Aufhebung des bezirksgerichtlichen Entscheids vom 4. April 2007 und die Gutheissung der Klage. Im Übrigen blieb der Entscheid des Bezirksgerichts unangefochten.
Mit Urteil vom 29. Januar 2010 wies das Obergericht des Kantons Zürich die Klage im Restbetrag von Fr. 590.60 ab.
B.c Mit Zirkulationsbeschluss vom 5. Juni 2011 hob das Kassationsgericht des Kantons Zürich das Urteil des Obergerichts vom 29. Januar 2010 auf und wies die Sache zur Neubeurteilung an das Obergericht zurück.
B.d Mit Urteil vom 21. November 2011 wies das Obergericht die Klage, soweit nicht bereits rechtskräftig beurteilt, im Restbetrag von Fr. 590.60 erneut ab.
Das Obergericht erwog, eine individuelle Abrede unter den Parteien hinsichtlich der Rückerstattung der Restprämie im Falle der Heirat könne nicht zustande gekommen sein, weil es dem Vermittlungsagenten S._ an der erforderlichen Bevollmächtigung zur Abgabe von Willenserklärungen fehlte bzw. weil eine schriftliche Bestätigung der Direktion der Rechtsvorgängerin der Beklagten für eine besondere Vereinbarung oder Abänderung des Vertrags nicht vorgelegen habe, und eine Berufung darauf auch nicht gegen Treu und Glauben verstosse. Eine Haftung für allfällig falsche Erklärungen oder eine falsche Auslegung der AVB des Vermittlungsagenten S._ sei mangels eines Schadens ebenfalls zu verneinen. Die unter den Parteien strittigen Behauptungen zum tatsächlichen Willen der Parteien müssten bei diesem Ergebnis nicht weiter abgeklärt werden.
Nachdem eine individuelle Abrede zwischen den Parteien nicht zustande gekommen sei, erachtete das Obergericht den durch Auslegung nach dem Vertrauensprinzip ermittelten Inhalt von Ziffer 27.3 der AVB für massgeblich. Hinsichtlich dieser Auslegung verweist das Obergericht auf die Erwägungen des Entscheids des Bezirksgerichts, das unter Würdigung aller Umstände eine gesetzeskonforme Auslegung vorgenommen habe, die auch von keiner Partei beanstandet worden sei.
C. Mit subsidiärer Verfassungsbeschwerde beantragt der Kläger dem Bundesgericht, es sei das Urteil des Obergerichts des Kantons Zürich vom 21. November 2011 (mit Ausnahme der Feststellung, dass die Kosten- und Entschädigungsregelung für das erstinstanzliche Verfahren bereits in Rechtskraft erwachsen sei) aufzuheben und die Beklagte zur Zahlung von Fr. 590.60 zu verpflichten. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. 1.1 Mit der subsidiären Verfassungsbeschwerde kann nur die Verletzung von verfassungsmässigen Rechten gerügt werden (<ref-law>). Diesbezüglich gilt eine qualifizierte Rügepflicht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 117 i.V.m. <ref-law>). Der Beschwerdeführer muss klar und detailliert anhand der Erwägungen des angefochtenen Entscheids darlegen, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-ruling> E. 1.2 S. 234; <ref-ruling> E. 2 S. 591 f.). Macht der Beschwerdeführer eine Verletzung von <ref-law> geltend, genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich; er hat vielmehr im Einzelnen zu zeigen, inwiefern der angefochtene Entscheid offensichtlich unhaltbar ist (<ref-ruling> E. 3 S. 352; <ref-ruling> E. 5.5 S. 5; <ref-ruling> E. 3.2 S. 444).
1.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>); neue Tatsachen und Beweismittel sind grundsätzlich unzulässig (Art. 117 i.V.m. <ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie auf einer Verletzung verfassungsmässiger Rechte beruht (Art. 116 i.V.m. <ref-law>). Wird Letzteres geltend gemacht, ist neben der Erheblichkeit der gerügten Tatsachenfeststellung für den Ausgang des Verfahrens klar und detailliert darzutun, inwiefern diese verfassungswidrig, insbesondere willkürlich, sein soll (<ref-ruling> E. 7.1 S. 398, 585 E. 4.1 S. 588 f.; je mit Hinweisen). Ausserdem hat der Beschwerdeführer mit Aktenhinweisen darzulegen, dass er entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen genannt hat (Urteile 4A_341/2011 vom 21. März 2012 E. 1.5.1; 4A_614/2011 vom 20. März 2012 E. 1.2; 4A_214/2008 vom 9. Juli 2008 E. 1.2, nicht publ. in: <ref-ruling>). Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (vgl. <ref-ruling> E. 1.3 S. 351 f., 393 E. 7.1 S. 398, 462 E. 2.4 S. 466 f.).
2. Der Beschwerdeführer rügt in verschiedener Hinsicht eine Verletzung des Willkürverbots (<ref-law>), des Anspruchs auf rechtliches Gehör (<ref-law>) und des Anspruchs auf ein faires Verfahren (Art. 6 Ziff. 1 EMRK).
2.1 Die Gehörs- und Willkürrügen hinsichtlich des Schlusssatzes in Erwägung 4.10 des angefochtenen Entscheids ("Wäre die Behauptung richtig gewesen, wäre es nicht zum vorliegenden Prozess gekommen") stossen ins Leere. Die Ausführungen des Beschwerdeführers sind schwer verständlich und es wird nicht klar, was er daraus ableiten will. Es kann ihm jedenfalls nicht gefolgt werden, wenn er im zitierten isolierten Satz eine unzulässige antizipierte Beweiswürdigung durch die Vorinstanz erblicken will. Zunächst geht aus seinen Vorbringen nicht hervor, welche von ihm konkret angebotenen Beweise infolge der beanstandeten Feststellung unberücksichtigt geblieben sein sollen, womit eine Gehörsverletzung von vornherein nicht hinreichend dargetan wird. Abgesehen davon kann dem Beschwerdeführer nicht gefolgt werden, wenn er der Vorinstanz eine Verletzung der aus <ref-law> abgeleiteten Begründungspflicht vorwirft. Wird der erwähnte Schlusssatz in seinem Zusammenhang gelesen, geht daraus hervor, dass die Vorinstanz in der betreffenden Erwägung die Rechtserheblichkeit der vom Beschwerdeführer behaupteten Information von S._ an den Vater des Beschwerdeführers unter der Annahme prüfte, dass es sich bei dieser Information - wie vom Beschwerdeführer behauptet - nicht um eine Zusicherung, sondern lediglich um eine Auslegung bzw. Erläuterung der AVB handelte. Sie erwähnte hierzu die beiden Hypothesen einer falschen sowie einer richtigen Information: War die angebliche Information, dass die Wahl der Zahlungsart der Prämie (Jahres-, Halbjahres- oder Vierteljahresprämie) keine Konsequenzen habe und die Jahresprämie im Heiratsfall pro rata zurückerstattet werde, falsch, sei aus dieser Auskunft kein Schaden entstanden, da selbst bei der Wahl einer Vierteljahresprämie die Prämie für den letzten Monat nicht zurückzuerstatten gewesen wäre. Wäre die behauptete Information demgegenüber richtig gewesen, so wäre es nach Ansicht der Vorinstanz nicht zum vorliegenden Prozess gekommen.
Damit hat die Vorinstanz ihren Entscheid hinreichend begründet. Der Beschwerdeführer zeigt nicht auf, inwiefern ihm die Begründung des angefochtenen Entscheids dessen sachgerechte Anfechtung verunmöglicht hätte (vgl. <ref-ruling> E. 4.2 S. 355; <ref-ruling> E. 4.1 S. 88; <ref-ruling> E. 3.3 S. 445; je mit Hinweisen). Entgegen der in der Beschwerde vertretenen Ansicht kann der Vorinstanz hinsichtlich der zitierten Feststellung auch keine Willkür vorgeworfen werden, wenn sie davon ausging, dass es nicht zum vorliegenden Prozess gekommen wäre, wenn die Information durch S._ richtig gewesen wäre. Wäre die Jahresprämie im Heiratsfall tatsächlich pro rata rückerstattet worden, wie dies S._ angeblich dem Vater des Beschwerdeführers mitgeteilt hatte, wäre die noch strittige Forderung auf Rückerstattung der Restprämie von Fr. 590.60 erfüllt worden. Unter diesen Voraussetzungen ist die vorinstanzliche Feststellung, es wäre nicht zu einem Zivilprozess gekommen, keineswegs unhaltbar, sondern vielmehr naheliegend.
Soweit der Beschwerdeführer in diesem Zusammenhang schliesslich vorbringt, die Vorinstanz habe "aufgrund dieses blossen Umkehrschlusses" zu Unrecht seine Behauptung als unzutreffend erachtet, wonach es sich bei den behaupteten Informationen von S._ nicht um eine Zusicherung, sondern lediglich um eine Auslegung bzw. Erläuterung gehandelt habe, kann ihm ebenfalls nicht gefolgt werden. Entsprechendes hat die Vorinstanz aus ihrer Feststellung nicht abgeleitet; entgegen der in der Beschwerde vertretenen Ansicht hat sie die Argumentation des Beschwerdeführers auch nicht etwa aufgrund eines Widerspruchs in dessen Begründung unbeachtet gelassen, sondern sie hat das erwähnte Vorbringen berücksichtigt, jedoch wegen Fehlens eines dadurch verursachten Schadens als unbehelflich erachtet. Entsprechend kann dem Beschwerdeführer auch nicht gefolgt werden, wenn er der Vorinstanz gestützt auf eine angeblich unterbliebene Prüfung vorwirft, sie habe zu seinem Nachteil in Verletzung seines Rechts auf ein faires Verfahren Sachverhaltsabklärungen und die Erhebung von Beweisen umgangen.
Die erhobenen Rügen, die Vorinstanz habe Art. 9 und 29 Abs. 2 BV sowie Art. 6 Ziff. 1 EMRK verletzt, sind unbegründet.
Die erhobenen Rügen, die Vorinstanz habe Art. 9 und 29 Abs. 2 BV sowie Art. 6 Ziff. 1 EMRK verletzt, sind unbegründet.
2.2 2.2.1 Der Beschwerdeführer bringt weiter vor, die Vorinstanz sei zwar zutreffend davon ausgegangen, er habe im vorinstanzlichen Verfahren sinngemäss geltend gemacht, die Beschwerdegegnerin habe den Agenten und dieser den Unteragenten mündlich bevollmächtigt, von Ziffer 27 der AVB abzuweichen. Sie habe in der Folge jedoch zu Unrecht auf eine Überprüfung der behaupteten Abreden verzichtet mit der Begründung, die behaupteten Abweichungen bedürften gemäss den AVB einer schriftlichen Bestätigung durch die Direktion der Rechtsvorgängerin der Beschwerdegegnerin, die unbestrittenermassen fehle. Eine Berufung auf die Formvorschrift, so der Beschwerdeführer weiter, widerspreche jedoch Treu und Glauben, was die Vorinstanz in Verletzung von <ref-law> verkannt habe.
2.2.2 Der Beschwerdeführer bringt im bundesgerichtlichen Beschwerdeverfahren nunmehr vor, die Beschwerdegegnerin, deren Direktorium und somit auch Direktor T._ hätten gewusst, dass eine mündlich überbrachte Abweichung von Ziffer 27.3 AVB nach den vertraglichen Formerfordernissen nicht gültig sein würde, und hätten trotzdem bewusst den Weg gewählt, die Mitteilung der angeblichen Abweichung ausschliesslich mündlich zu überbringen. Der Beschwerdeschrift lässt sich nicht entnehmen, dass der Beschwerdeführer entsprechende tatsächliche Vorbringen hinsichtlich der behaupteten Vorgehensweise bereits im vorinstanzlichen Verfahren erhoben hätte, weshalb diese unbeachtlich sind (vgl. <ref-law>).
Im Übrigen verkennt der Beschwerdeführer mit seinen Vorbringen, dass das Bundesgericht im Rahmen der subsidiären Verfassungsbeschwerde nicht frei überprüfen kann, ob die vorinstanzliche Erwägung zutrifft, wonach die Berufung der Beschwerdegegnerin auf das vertragliche Formerfordernis bei Vorliegen der behaupteten Umstände Treu und Glauben (<ref-law>) widerspricht. Mit seinen appellatorischen Vorbringen zeigt er keine Verletzung von <ref-law> auf.
3. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).
Die Beschwerdegegnerin beantragt, es sei die Prozessentschädigung zuzüglich Mehrwertsteuer zuzusprechen. Bei der Bemessung der Parteientschädigung wird die Mehrwertsteuer im Rahmen des geltenden Tarifs pauschal berücksichtigt (Art. 12 des Reglements über die Parteientschädigung und die Entschädigung für die amtliche Vertretung im Verfahren vor dem Bundesgericht [SR 173.110.210.3]).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
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, 24. Mai 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann