Sachverhalt:
A. Seit dem Jahre 1989 war A._ (Arbeitnehmer, Kläger, Beschwerdeführer) für die X._ AG (Arbeitgeberin, Beklagte, Beschwerdegegnerin), vormals Y._ AG, als Geschäftsführer tätig. Zwanzig Monate vor seiner ordentlichen Pensionierung unterbreitete ihm die Arbeitgeberin drei verschiedene Änderungsofferten, die unter anderem eine Reduktion seines Monatslohnes, eine Änderung seiner Funktion und eine kürzere Kündigungsfrist vorsahen. Nachdem der Arbeitnehmer auch die dritte Änderungsofferte nicht akzeptierte, kündigte die Arbeitgeberin das Arbeitsverhältnis unter Einhaltung der sechsmonatigen Kündigungsfrist auf den 31. Juli 2009.
Aufgrund des hohen Ferienguthabens des Arbeitnehmers, welches im Kündigungszeitpunkt 119,5 Tage betrug, erstellte die Arbeitgeberin dem Arbeitnehmer am 2. Februar 2009 einen Ferienplan, worin sie ihm bis zum Ablauf seiner Kündigungsfrist (bis auf ein paar wenige Arbeitstage) Ferien anordnete.
B. B.a Am 9. April 2009 reichte der Arbeitnehmer beim Arbeitsgericht Zürich Klage ein mit dem Antrag, es sei festzustellen, dass die Kündigung des Arbeitsverhältnisses missbräuchlich erfolgt sei, und es sei die Arbeitgeberin zu verpflichten, ihm eine Entschädigung von fünf Monatslöhnen im Betrag von Fr. 95'400.-- zu bezahlen. Anlässlich der Hauptverhandlung ergänzte der Kläger seine Begehren und beantragte eine Entschädigung von Fr. 97'250.--, den Ersatz von Spesen im Umfang von Fr. 1'237.45, die Bezahlung von Fr. 90'162.45 für nicht bezogene Ferien und die Aus- und Zustellung eines Arbeitszeugnisses.
Mit Urteil vom 25. Januar 2011 hiess das Arbeitsgericht Zürich das Begehren auf Leistung einer Entschädigung infolge missbräuchlicher Kündigung im Umfang von Fr. 50'760.-- sowie den geltend gemachten Ferienanspruch im Umfang von Fr. 55'518.75 brutto bzw. Fr. 52'159.85 netto gut.
B.b Mit Urteil vom 22. Februar 2012 hiess das Obergericht des Kantons Zürich die gegen das Urteil des Arbeitsgerichts Zürich vom 25. Januar 2011 durch die Beklagte erhobene Berufung teilweise gut und reduzierte die Entschädigung für den geltend gemachten Ferienanspruch auf Fr. 15'101.10 brutto bzw. Fr. 14'187.50 netto zuzüglich Zins zu 5 % seit dem 1. August 2009, wobei es die Entschädigung infolge missbräuchlicher Kündigung im Umfang von Fr. 50'760.-- bestätigte.
C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, Ziffer 1 des Urteils des Obergerichts des Kantons Zürich vom 22. Februar 2012 sei aufzuheben und die Beklagte sei zu verpflichten, ihm Fr. 50'760.-- netto zuzüglich 5 % Zins seit dem 9. April 2009 sowie Fr. 55'518.75 brutto bzw. Fr. 52'159.85 netto zuzüglich 5 % Zins seit dem 1. August 2009 zu bezahlen; eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Sodann seien Ziffer 3 und 4 (Kosten- und Parteientschädigung für das erstinstanzliche Verfahren) sowie Ziffer 6 und 7 (Kosten- und Parteientschädigung für das zweitinstanzliche Verfahren) des Urteils des Obergerichts aufzuheben und es seien die Kosten- und Entschädigungsfolgen des erst- und zweitinstanzlichen Verfahrens nach Massgabe des Verfahrensausgangs vor Bundesgericht neu festzusetzen; eventualiter sei die Sache zur Neufestsetzung der erst- und zweitinstanzlichen Kosten- und Entschädigungsfolgen an die Vorinstanz zurückzuweisen.
Die Beklagte beantragt die Abweisung der Beschwerde; die Vorinstanz hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (Art. 29 Abs. 1 BGG; <ref-ruling> E. 1 S. 417 mit Hinweisen).
Das angefochtene Urteil des Obergerichts des Kantons Zürich ist ein verfahrensabschliessender Endentscheid (Art. 90 BGG) einer letzten kantonalen Instanz (Art. 75 Abs. 1 BGG) über eine Forderung aus Arbeitsvertrag. Der erforderliche Streitwert nach Art. 74 Abs. 1 lit. a BGG ist erreicht. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde - unter Vorbehalt einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG) - einzutreten.
2. In tatsächlicher Hinsicht legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.5 S. 401).
Der Beschwerdeführer stellt seinen Rügen zunächst eine "Zusammenfassung der Erwägungen der Vorinstanzen" voran. Insoweit der Beschwerdeführer dabei von den tatsächlichen Feststellungen der Vorinstanz abweicht, ist er nicht zu hören.
3. Nach Art. 42 Abs. 2 BGG ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt.
Der Beschwerdeführer stellt in seiner Beschwerdeschrift den Antrag, die Ziffern 3, 4, 6 und 7 des angefochtenen Entscheids - die Kosten für das erst- und zweitinstanzliche Verfahren sowie die Parteientschädigung für beide kantonalen Verfahren - seien aufzuheben und die Kosten- und Entschädigungsfolgen neu festzusetzen. Soweit der Beschwerdeführer mit diesem Antrag verlangen wollte, die Kosten der kantonalen Verfahren seien auch bei Abweisung der Beschwerde anders zu verlegen, fehlt jede Begründung (Art. 42 BGG). Auf diesen Antrag ist nicht einzutreten.
4. Die Vorinstanz qualifizierte die gegen den Beschwerdeführer ergangene Kündigung - welche ihm nach zwanzigjähriger Tätigkeit kurz vor seiner ordentlichen Pensionierung ausgesprochen wurde, weil er eine Änderung seines Arbeitsvertrages zu seinen Lasten nicht akzeptierte - als missbräuchlich. In Bestätigung des erstinstanzlichen Urteils sprach sie ihm eine Entschädigung in der Höhe von drei Monatslöhnen bzw. Fr. 50'760.-- zu, was nicht mehr streitig ist.
Streitig ist vor Bundesgericht nur noch die Reduktion des von der Beschwerdegegnerin abzugeltenden Ferienguthabens. Das Arbeitsgericht setzte die Entschädigung für nicht bezogene Ferientage ex aequo et bono auf Fr. 55'518.75 brutto bzw. Fr. 52'159.85 netto fest. Die Vorinstanz reduzierte in der Folge das abzugeltende Ferienguthaben auf Fr. 15'101.10 brutto bzw. Fr. 14'187.50 netto.
4.1 Die Vorinstanz hat erwogen, dass es der Beschwerdeführer als Geschäftsführer erheblich mitzuvertreten habe, dass sein Ferienguthaben auf 119,5 Tage angewachsen sei. Er sei mit der Anordnung der Beschwerdegegnerin zum Ferienbezug während der Kündigungsfrist von seinen Verpflichtungen gegenüber der Beschwerdegegnerin grundsätzlich entbunden gewesen. Der Beschwerdeführer habe keine konkreten Bemühungen um eine neue Arbeitsstelle angeführt und er habe ebenso wenig dargetan, dass ein Grund vorgelegen habe, sich über die Ferienanordnung der Beschwerdegegnerin hinwegzusetzen. Damit seien dem Beschwerdeführer von den unbestrittenen 104,5 Arbeitstagen im Zeitraum von März bis Juli 2009 insgesamt sechs (von der Beschwerdegegnerin anerkannte) Arbeitstage anzurechnen, womit 98,5 Tage als angeordneter Ferienbezug zu berücksichtigen seien. Damit seien dem Beschwerdeführer 17 Ferientage (unter Berücksichtigung der vier bereits ausbezahlten Ferientage) auszubezahlen.
4.2 Der Beschwerdeführer bringt vor, die Vorinstanz habe mit der Reduktion des abzugeltenden Ferienguthabens Art. 329 Abs. 3 und Art. 329c OR verletzt.
Entgegen der Meinung der Vorinstanz, treffe ihn keine "Mitverantwortung" am hohen Feriensaldo. Es sei Pflicht des Arbeitgebers, dafür zu sorgen, dass der Arbeitnehmer seine Ferien während des laufenden Dienstjahres beziehe. Sodann müsse dem Arbeitnehmer während der Kündigungs- oder Freistellungsfrist genügend Zeit für die Stellensuche eingeräumt werden; demnach dürften Ferien nur bezogen werden, wenn für die Arbeitssuche noch genügend Zeit verbleibe. Die Vorinstanz habe ihm jedoch während der sechsmonatigen Kündigungsfrist keinen einzigen Tag für die Arbeitssuche gewährt, was bundesrechtswidrig sei.
Zudem sei die Feststellung der Vorinstanz, wonach er keine konkreten Bemühungen um eine neue Arbeitsstelle angeführt habe, offensichtlich unrichtig. Dabei beruft sich der Beschwerdeführer auf seine Ausführungen vor dem Arbeitsgericht und macht geltend, er habe sich um eine neue Arbeitsstelle bemüht bzw. seine Tätigkeiten im Zeitraum von März bis Ende Juli 2009 hätten darauf gezielt, "im Markt zu bleiben". Diese Behauptung sei vor erster Instanz unbestritten geblieben und hätte auch vor Obergericht als anerkannt zu gelten.
4.3 Mit seiner Sachverhaltsrüge vermag der Beschwerdeführer keine Willkür auszuweisen. Seine allgemeine Behauptung, er sei auf der Suche nach einer neuen Arbeitsstelle gewesen, kann ohne in Willkür zu verfallen nicht als hinreichende Substanziierung konkreter Bemühungen um eine neue Arbeitsstelle angesehen werden. Nachdem die Beschwerdegegnerin im Übrigen die Abgeltung der Ferien beim Obergericht angefochten hat, kann sich der Beschwerdeführer nicht darauf beschränken, auf die entsprechenden Ausführungen der ersten Instanz zu verweisen. Er hätte konkret darlegen müssen, worin seine Bemühungen im Einzelnen bestanden haben, was er weder vor erster noch vor zweiter Instanz getan hat, wie dies die Vorinstanz willkürfrei angenommen hat.
4.4 Nach der Rechtsprechung des Bundesgerichts ist der Zweck der Ferien die Erholung des Arbeitnehmers. Der Anspruch auf Ferien hat rechtlich eine Doppelnatur. Einerseits stellt er eine Forderung des Arbeitnehmers dar; andererseits ist er als Ausfluss der Fürsorgepflicht des Arbeitgebers anzusehen. Die Ferien dürfen während der Dauer des Arbeitsverhältnisses nicht durch Geld abgegolten werden (Art. 329d Abs. 2 OR), sondern sind tatsächlich zu beziehen. Das Abgeltungsverbot ist gemäss Art. 361 OR absolut zwingend. Daher müssen die Ferien auch während der Kündigungsfrist grundsätzlich in natura bezogen werden. Eine Ausnahme vom Abgeltungsverbot gilt nur, wenn der Bezug der Ferien in der bis zur Beendigung des Arbeitsverhältnisses verbleibenden Zeit nicht möglich oder zumutbar ist. Der Arbeitnehmer muss jedenfalls in dieser Zeit die Möglichkeit haben, nach einer neuen Stelle zu suchen, denn Art. 329 Abs. 3 OR bestimmt, dass dem Arbeitnehmer nach erfolgter Kündigung die für das Aufsuchen einer anderen Arbeitsstelle erforderliche Zeit zu gewähren ist (vgl. <ref-ruling> E. 4 a/aa S. 280 f.).
Da die Suche nach einer neuen Arbeitsstelle mit dem Erholungszweck der Ferien grundsätzlich unvereinbar ist, muss im Einzelfall in Betrachtung der Gesamtumstände geprüft werden, wie es sich mit dem vom Arbeitgeber angeordneten Ferienbezug während der Kündigungsfrist verhält. Dabei muss auf die Dauer der Kündigungsfrist, die Arbeitsmarktlage, das verbleibende Ferienguthaben und die persönlichen Voraussetzungen des Arbeitnehmers, wie sein Alter oder seine beruflichen Fähigkeiten Rücksicht genommen werden (Urteil 4C.84/2002 vom 22. Oktober 2002 E. 3.2.1; vgl. auch ERIC CEROTTINI, Le droit aux vacances, Diss. Lausanne 2001, S. 298; ALFRED BLESI, Die Freistellung des Arbeitnehmers, 2. Aufl. 2010, S. 164 f.).
4.5 Die Vorinstanz hat zu Recht erwogen, dass die Beschwerdegegnerin den Beschwerdeführer nicht freigestellt hat, sondern ihm bis zum Ablauf seiner sechsmonatigen Kündigungsfrist den Bezug seines Ferienguthabens angeordnet hat. Dem Beschwerdeführer wurde im Ferienplan - bis auf ein paar wenige Arbeitstage - Tag für Tag Ferien zugewiesen; es wurde genau bestimmt, wann er seine Ferien zu beziehen habe.
Die Anordnung von Ferien während der Kündigungsfrist ist dann zulässig, wenn der Bezug der Ferien während dieser Zeit möglich und zumutbar ist (vgl. E. 4.4 hievor). Nach den verbindlichen Feststellungen der Vorinstanz, hat kein Grund vorgelegen, dass sich der Beschwerdeführer über die Ferienanordnung der Beschwerdegegnerin hätte hinwegsetzen müssen. Er sei von seinen Verpflichtungen gegenüber der Beschwerdegegnerin entbunden gewesen und habe demnach bis auf ein paar wenige Tage keine Arbeitsleistung mehr erbringen müssen. Der Beschwerdeführer bringt nicht vor, dass der Ferienplan seitens der Beschwerdegegnerin nicht eingehalten worden wäre oder dass man ihn während seinen Ferien zur Arbeit gezwungen hätte; demnach war der Ferienbezug während der Kündigungsfrist für den Beschwerdeführer durchaus möglich.
Der Beschwerdeführer macht auch nicht geltend, dass ihm der angeordnete Ferienbezug keine Erholung gebracht hätte oder dass der Erholungszweck der Ferien durch den Ferienplan vereitelt worden wäre. Aus seinen Ausführungen geht nicht hervor, inwiefern der Ferienbezug während der Kündigungsfrist für ihn unzumutbar gewesen wäre; im Gegenteil, er bringt sogar selber vor, dass es ihm im Juli 2009 möglich gewesen sei, drei Wochen ununterbrochen Ferien zu beziehen. Der Beschwerdeführer beschränkt seine Rüge einzig auf die Tatsache, dass man ihm keinen Tag zur Stellensuche gewährt habe. Es steht jedoch nach den verbindlichen Feststellungen der Vorinstanz fest, dass er sich während der Kündigungsfrist nicht konkret um eine neue Stelle bemüht hat, was aufgrund seines Alters im Kündigungszeitpunkt von 63,5 Jahren auch plausibel erscheint.
4.6 Mit der Vorinstanz ist davon auszugehen, dass es der Beschwerdeführer erheblich mitzuvertreten hat, dass sein Feriensaldo auf 119,5 Tage angewachsen ist. Er hat es als ehemaliger Geschäftsführer der Beschwerdegegnerin selber in der Hand gehabt, wann er seine Ferien während der Anstellungsdauer hat beziehen wollen; es erscheint nahezu missbräuchlich, wenn der Beschwerdeführer vorbringt, man hätte ihm - als Geschäftsführer - den Ferienbezug während des laufenden Dienstjahres vorschreiben sollen.
Angesichts der sechsmonatigen Kündigungsfrist des Beschwerdeführers war der Bezug der angeordneten Ferien während dieser Zeit durchaus möglich und zumutbar. Die Vorinstanz hat keine Bundesrechtsverletzung begangen, indem sie 98,5 Tage als angeordneten Ferienbezug berücksichtigt hat.
5. Nach dem Gesagten ist die Beschwerde 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).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 11. September 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Die Gerichtsschreiberin: Reitze