Sachverhalt:
A. X._ war seit längerer Zeit Kunde der damaligen Bank Y._ (Y._) und heutigen Bank Z._, Filiale A._.
Am 28. Juni 1996 kaufte er 4'500 Namenaktien der W._ AG von der Y._ zum Preis von je Fr. 9.25, insgesamt für einen Betrag von Fr. 42'120.45 (einschliesslich Kommission und Gebühren). Am 21. Januar 1997 wurde der Konkurs über die W._ AG eröffnet. X._ geht davon aus, dass die Y._ beim Verkauf von Aktien der W._ AG ab Februar 1996 sein Vertrauen missbraucht habe.
B. B.a Mit Klage vom 5. März 2002 beantragte X._ (Kläger) dem Bezirksgericht Hinwil die Verurteilung der (damaligen) Y._ (Beklagte) zur Bezahlung von Fr. 42'120.45.-- zuzüglich Zins zu 5% seit 3. Juli 1996, unter Kosten- und Entschädigungsfolge zu Lasten der Beklagten.
Mit Urteil vom 13. Juli 2010 wies das Bezirksgericht die Klage vollumfänglich ab.
B.b Dagegen erhob der Kläger Berufung an das Obergericht des Kantons Zürich.
Mit Urteil vom 12. April 2012 wies das Obergericht die Berufung ab.
Es ging davon aus, dass bei einem Verkauf von Aktien der W._ AG aus Eigenbeständen der Y._ am 28. Juli 1996 von einer Treuwidrigkeit und damit von einem Verstoss gegen <ref-law> auszugehen wäre, hielt aber den dem Kläger auferlegten Beweis einer Lieferung aus Eigenbeständen nicht für erbracht.
C. Mit Beschwerde in Zivilsachen vom 18. Mai 2012 liess X._ (Beschwerdeführer) die Aufhebung des obergerichtlichen Urteils beantragen und seine vor dem Bezirksgericht Hinwil gestellten Rechtsbegehren erneuern.
Mit Vernehmlassung vom 17. Januar 2012 liess die Bank Z._ (Beschwerdegegnerin) Abweisung der Beschwerde beantragen. Die Vorinstanz verzichtete auf Vernehmlassung.
Die Parteien reichten Replik und Duplik ein.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1; <ref-ruling> E. 1 S. 103, 470 E. 1 S. 472; <ref-ruling> E. 1 S. 216).
1.1 Die Beschwerde richtet sich gegen einen verfahrensabschliessenden Rechtsmittelentscheid eines oberen kantonalen Gerichts (<ref-law> i.V.m. <ref-law>). Sie ist (unter Berücksichtigung des Auffahrtsdonnerstages - 17. Mai 2012 - als Feiertag) innert der Beschwerdefrist (<ref-law>) von der mit ihren Rechtsbegehren unterlegenen Partei (<ref-law>) eingereicht worden. Bei der Streitsache handelt es sich um eine Zivilsache (<ref-law>) mit einem Streitwert von über Fr. 30'000.-- (<ref-law>). Auf die Beschwerde ist unter Vorbehalt einer rechtsgenügenden Begründung (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG) einzutreten.
1.2 Mit der Beschwerde in Zivilsachen kann u.a. die Verletzung von Bundesrecht einschliesslich Bundesverfassungsrecht gerügt werden (<ref-law>; <ref-ruling> E. 1.2 S. 382). Nicht zu den in <ref-law> vorgesehenen Rügegründen gehört hingegen die Verletzung der kantonalen Zivilprozessordnung, deren Anwendung und Auslegung das Bundesgericht einzig unter dem Blickwinkel eines Verstosses gegen Bundesrecht oder gegen Bundesverfassungsrecht beurteilen kann (<ref-ruling> E. 2.4; <ref-ruling> E. 4.3 S. 521; <ref-ruling> E. 1.2 S. 382 f.).
Auf das Verfahren vor der Vorinstanz fand die nunmehr aufgehobene Zivilprozessordnung des Kantons Zürich Anwendung. Soweit die Verletzung von Normen des kantonalen Zivilprozessrechts gerügt wird, ist in der Beschwerdeschrift mithin darzutun, dass dabei auch ein Verstoss gegen Bundes- oder Bundesverfassungsrecht vorliegt (vgl. Urteil 4A_339/2011 vom 23. November 2011 E. 1.4).
1.3 Das Bundesgericht wendet das Recht zwar von Amtes wegen an (<ref-law>; vgl. dazu <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Unter Berücksichtigung der Begründungspflicht (<ref-law>) prüft es dabei aber nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 2.2; <ref-ruling> E. 1.4.1 S. 254 mit Hinweisen).
2. Der Beschwerdeführer rügt eine Verletzung des rechtlichen Gehörs, die er in der Missachtung der Begründungspflicht durch die Vorinstanz erblickt. Das Obergericht habe zwar angenommen, die Beschwerdegegnerin hätte beim Verkauf der Aktien aus dem Eigenbestand eine Treuepflichtverletzung begangen; es habe aber nicht begründet, weshalb - wie der Beschwerdeführer im kantonalen Verfahren gehörig behauptet habe - eine Treuepflichtverletzung nicht auch dann anzunehmen wäre, wenn die Beschwerdegegnerin die Aktien über die Börse bezogen hätte. Die Frage sei rechtserheblich, weil die Vorinstanz zum Schluss gelangt sei, die Beschwerdegegnerin habe die Aktien nicht aus ihren eigenen Beständen verkauft. Der Beschwerdeführer räumt allerdings selber ein, dass die Vorinstanz auf die Rechtsfrage doch - wenn auch nur am Rande - eingegangen sei. Die Frage kann indessen offen bleiben, falls die Feststellung der Vorinstanz, die Beschwerdegegnerin habe die Aktien nicht aus ihrem Eigenbestand verkauft, sich als rechtsfehlerhaft erweist.
3. Der Beschwerdeführer rügt, die Vorinstanz habe den Sachverhalt willkürlich und in Verletzung bundesrechtlicher Beweisvorschriften, insbesondere <ref-law>, insofern unrichtig festgestellt, als sie davon ausging, die Beschwerdegegnerin habe die dem Beschwerdeführer verkauften Aktien über die Börse beschafft.
3.1 Die erste Instanz hat dem Kläger (Beschwerdeführer) den Beweis dafür aufgelegt, dass er 4'500 Namenaktien der W._ AG aus Eigenbeständen der damaligen Y._ erworben habe. Als einziges Beweismittel hat der Kläger eine von der Y._ erstellte Wertschriftenabrechnung vom 28. Juni 1996 eingereicht. In dieser erklärte die Y._, sie habe die Aktien dem Beschwerdeführer "aufgrund der Statuten und Usanzen der Zürcher Effektenbörse als Selbstkontrahent" verkauft. Beide kantonalen Instanzen hielten diese Urkunde nicht für geeignet, die Herkunft der Aktien zu beweisen. Die Vorinstanz erwog, die Wertschriftenabrechnung besage lediglich, dass die Y._ den Auftrag aufgrund der Statuten und Usanzen der Zürcher Effektenbörse als "Selbstkontrahent" ausgeführt habe. Das genüge angesichts der Bestreitungen der Beklagten nicht für den Nachweis, dass die Y._ die an den Kläger verkauften Aktien der W._ AG aus den Eigenbeständen bezogen habe. Bezüglich dieser Frage ging die Vorinstanz mithin zulasten des Klägers von Beweislosigkeit aus.
3.2 Demgegenüber vertritt der Beschwerdeführer die Ansicht, die Beschwerdegegnerin trage die Beweislast für ihre Behauptung, wonach die an den Kläger verkauften Aktien über die Börse gekauft worden seien, weil sie aus diesem Umstand für sich Rechte im Sinne von <ref-law> ableiten wolle.
3.3 Nach <ref-law> hat, wo das Gesetz es nicht anders bestimmt, derjenige das Vorhandensein einer behaupteten Tatsache zu beweisen, der aus ihr Rechte ableitet. Beim Kommissionsvertrag wird die Beweislastgrundregel des <ref-law> durch eine gesetzliche Vermutung ergänzt: Bei Kommissionen zum Einkauf von Wertpapieren, die einen Börsenpreis haben, ist die Kommissionärin, wenn der Kommittent nicht etwas anderes bestimmt hat, befugt, die Wertpapiere, die sie einkaufen soll, als Verkäuferin selbst zu liefern (<ref-law>). Meldet die Kommissionärin in den Fällen, wo der Eintritt als Eigenhändlerin zugestanden ist, die Ausführung des Auftrages, ohne eine andere Person als Verkäuferin namhaft zu machen, so ist anzunehmen, dass sie selbst die Verpflichtung einer Verkäuferin auf sich genommen habe (<ref-law>).
3.4 Die Vorinstanz erwog, es sei in Wertschriftenabrechnungen häufig auch dann von einem Selbsteintritt, von "Selbstkontrahent" die Rede, wenn der Auftrag über die Börse abgewickelt wurde. Die Behauptung der Beklagten, dass von einem unechten Selbsteintritt auszugehen sei und die fraglichen Aktien an der Börse erworben wurden, sei daher mit der vom Kläger eingereichten Wertschriftenabrechnung nicht widerlegt.
3.5 Der Beschwerdeführer rügt, es könne nicht Sache des Klägers sein, die Entlastungsbehauptung der Beklagten, wonach von einem unechten Selbsteintritt auszugehen sei, zu widerlegen.
3.5.1 Der Gesetzeswortlaut von <ref-law> unterscheidet nicht zwischen einem echten und einem unechten Selbsteintritt, sondern knüpft schlicht an den Inhalt der Ausführungsmeldung des Kommissionärs an. Teilt dieser die Ausführung des Auftrages mit, ohne eine andere Person als Verkäufer zu nennen, so ist der Eintritt als Eigenhändler i.S.v. <ref-law> anzunehmen bzw. - ausweislich des Randtitels zu <ref-law> - zu vermuten. Dies gilt in den Fällen, wo der Eintritt als Eigenhändler zugestanden ist, was gemäss <ref-law> u.a. zutrifft, wenn, wie im vorliegenden Fall, der Auftrag den Einkauf von Wertpapieren betrifft, die einen Börsenpreis haben, und der Kommittent nicht etwas anderes bestimmt hat. Diesfalls ist der Kommissionär befugt, statt die Wertpapiere bei einem Dritten einzukaufen, diese selbst als Verkäufer zu liefern.
3.5.2 In der Lehre ist die Ansicht anzutreffen, dass zu unterscheiden sei, ob der Kommissionär dem Kommittenten die Ausführung des Geschäfts ohne Bezeichnung der Gegenpartei meldet, bevor er überhaupt ein Drittgeschäft abgeschlossen (VON PLANTA/LENZ, in: Basler Kommentar, 5. Aufl. 2011, N. 2a zu <ref-law> sowie VON PLANTA/ FLEGBO-BERNEY, in: Commentaire romand, 2. Aufl. 2012, N. 2a zu <ref-law>) oder aber nachdem er mit einem Dritten das Erwerbsgeschäft abgeschlossen hat (VON PLANTA/LENZ, a.a.O., N. 2b zu <ref-law> sowie VON PLANTA/FLEGBO-BERNEY, a.a.O., N. 2b zu <ref-law>). Im zweiten Fall soll <ref-law> nicht zur Anwendung kommen, weil mit dem Abschluss des Drittgeschäfts das Selbsteintrittsrecht des Kommissionärs untergegangen sei. Wäre dem nicht so, könnte der Kommissionär je nach Marktpreisentwicklung den Selbsteintritt erklären bzw. darauf verzichten und so die guten Geschäfte für sich behalten, die schlechten jedoch an den Kommittenten weitergeben (HOFSTETTER, SPR VII/6, 2000, S. 211 f., Ziff. 2d).
3.5.3 Der Gesetzeswortlaut bietet für eine solche Unterscheidung keine Stütze. In jedem Falle aber hätte diese den Zweck, den Kommittenten vor der Auswirkung des latenten Interessenkonflikts des Eigenhändlers zu schützen. Auf den vorliegenden Fall übertragen, würde sie das Gegenteil bewirken: Dem Kommittenten würde in der Frage, ob überhaupt ein Selbsteintritt vorliege, das Beweisrisiko zugeschoben.
Die Frage kann indessen offenbleiben, weil im vorliegenden Fall nicht die Preisgestaltung strittig ist, sondern die Herkunft der von der Beschwerdegegnerin gelieferten Aktien. Indem sich die Beschwerdegegnerin in ihrer Wertschriftenabrechnung bezüglich der Ausführung des Auftrages als Selbstkontrahentin bezeichnete, ohne eine andere Person als Verkäuferin zu nennen, löste sie die Vermutung aus, sie habe als Kommissionärin im Sinne von Art. 437 i.V.m. 436 Abs. 1 OR von der Befugnis Gebrauch gemacht, auf den Einkauf der Aktien, die sie einkaufen sollte, bei einem Dritten zu verzichten, weil sie entsprechende Wertpapiere bereits in ihrem Eigentum hatte (GAUTSCHI, Berner Kommentar, 1962, N. 1b zu <ref-law>). Die Vermutung ist widerlegbar (GAUTSCHI, a.a.O; TERCIER/FAVRE/PEDRAZZINI, Les contrats spéciaux, 4. Aufl. 2009, N. 5878); die Beweislast der Widerlegung durch Nachweis eines Börsenkaufs trägt aber die Beschwerdegegnerin als Kommissionärin (HANS PETER WALTER, in: Berner Kommentar, 2012, N. 412, 428 zu <ref-law>). Indem die Vorinstanz die Beweislast bezüglich der Beschaffungsweise der Aktien dem Beschwerdeführer auferlegte, verletzte sie Art. 436 Abs. 1 und 437 OR i.V.m. <ref-law>.
4. Die Beschwerde erweist sich damit als begründet. Der angefochtene Entscheid ist aufzuheben und die Sache an die Vorinstanz zur Neubeurteilung unter Berücksichtigung der korrekten Beweislastverteilung zurückzuweisen.
Diesem Ausgang des Verfahrens entsprechend wird die Beschwerdegegnerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen.
2. Der angefochtene Entscheid wird aufgehoben und die Sache an die Vorinstanz zur Neuentscheidung zurückgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden der Beschwerdegegnerin auferlegt.
4. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 21. November 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Hurni