Sachverhalt: A. A._ (Beschwerdeführer) war ab 1. Juli 1997 durch die YZ._ AG als Geschäftsführer der in Tschechien domizilierten YQ._ angestellt worden. Am 8. Mai 2003 wurde das Anstellungsverhältnis rückwirkend per 30. April 2003 aufgelöst. Mit Wirkung ab 1. Juli 2003 war der Beschwerdeführer in geschäftsführender Funktion bei der Firma X._ AG (Beschwerdegegnerin) tätig. Diese kündigte das Arbeitsverhältnis am 4. September 2006 namentlich infolge Verdachts auf betrügerische Handlungen fristlos. Der Beschwerdeführer bestritt in der Folge die gegen ihn erhobenen Vorwürfe. B. Am 5. Dezember 2006 klagte der Beschwerdeführer beim Kantonsgericht Schaffhausen eine arbeitsvertragliche Forderung in Höhe von Fr. 29'999.-- nebst Zins zu 5 % seit dem 4. September 2006 ein. Als Begründung gab er an, die Beschwerdegegnerin schulde ihm wegen ungerechtfertiger fristloser Entlassung die Monatslöhne September 2006 bis Januar 2007 zuzüglich Spesen (im Betrag von Fr. 20'500.--), den 13. Monatslohn für das ganze Jahr 2006 und anteilsmässig für Januar 2007 (im Betrag von Fr. 4'441.65) sowie Lohnersatz gemäss Art. 337c Abs. 3 OR. Nach Durchführung einer Haupt- und einer Beweisverhandlung wies das Kantonsgericht die Klage mit Urteil vom 27. Januar 2011 ab; auf Grund mutwilliger Klageführung auferlegte es dem Beschwerdeführer Verfahrenskosten in Höhe von insgesamt Fr. 14'410.-- (Fr. 6'000.-- Staatsgebühr und Fr. 8'410.-- Barauslagen) sowie eine zuhanden der Beschwerdegegnerin zu leistende Parteientschädigung von Fr. 17'000.--. Es erwog dabei zusammenfassend, dass der Beschwerdeführer unberechtigt, d.h. ohne Einverständnis der Beschwerdegegnerin, mit sich selber einen zweiten Arbeitsvertrag als Geschäftsführer der YQ._ abgeschlossen und sich so ein zweites Gehalt habe auszahlen lassen. Zudem habe er während seiner Tätigkeit bei der YQ._ von der Firma R._ monatliche Bonuszahlungen für Treibstoffeinkäufe im Betrag von durchschnittlich 20'000.-- Tschechischen Kronen (CZK; entspricht etwa Fr. 1000.-- [vgl. http://de.exchange-rates.org/Rate/CHF/CZK, besucht am 30. März 2012]) für sich selbst behalten, welche der Arbeitgeberin zugestanden hätten. Diese zwei Verfehlungen stellten wichtige Gründe dar, welcher jeder für sich eine fristlose Kündigung des Arbeitsvertrages durch die Beschwerdegegnerin rechtfertigte. Die dagegen erhobene Berufung wies das Obergericht des Kantons Schaffhausen ab (Urteil vom 23. September 2011, Dispositiv-Ziffer 1); allein der Umstand, dass der Beschwerdeführer während seiner Tätigkeit für die YQ._ Bonuszahlungen für Treibstoffeinkäufe in der Höhe von rund CZK 20'000.-- monatlich für sich behalten habe, anstatt sie der Arbeitgeberin abzuliefern, sei objektiv geeignet gewesen, das gegenseitige Vertrauen der Vertragsparteien zu zerstören. Durch sein Verhalten habe der Beschwerdeführer somit einen wichtigen Grund gesetzt, der die Beschwerdegegnerin berechtigt habe, ihm fristlos zu kündigen. Es verpflichtete den Beschwerdeführer - in gleichzeitiger Bestätigung der vorinstanzlichen Kosten- und Entschädigungsauflage - zufolge mutwilliger Prozessführung zur Bezahlung einer Staatsgebühr von Fr. 3'000.-- (Dispositiv-Ziffer 2) sowie eines Parteikostenersatzes von Fr. 2'511.85 (Dispositiv-Ziffer 3). C. Mit Beschwerde in Zivilsachen lässt der Beschwerdeführer beantragen, in Aufhebung des obergerichtlichen Urteils sei die Beschwerdegegnerin zu verpflichten, ihm Fr. 29'999.-- nebst Zins zu 5 % seit dem 4. September 2006 zu bezahlen. Eventualiter seien die Dispositiv-Ziffern 2 und 3 des vorinstanzlichen Urteils aufzuheben. Die Übersetzungskosten seien der Beschwerdegegnerin aufzubürden oder aber zusammen mit den Barauslagen vom Staat zu tragen. Auf die Erhebung einer Staatsgebühr sei zu verzichten. Subeventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Das Obergericht und die Beschwerdegegnerin schliessen auf Abweisung der Beschwerde. 