Sachverhalt: A. A.a Am 1. Mai 2009 erwarb A._ (Käufer, Kläger, Beschwerdeführer) an einer von der X._ International GmbH (Verkäuferin, Beklagte, Beschwerdegegnerin) durchgeführten Versteigerung einen Personenwagen Lancia. Der Kaufpreis betrug Fr. 40'000.-- zuzüglich 12 % Verkaufsprovision, insgesamt Fr. 44'800.--. Das Beweisverfahren hat ergeben, dass die Verkäuferin im Zeitpunkt der Versteigerung Eigentümerin des Lancias war. Anlässlich der Auktion standen dem Käufer die Auktionsbedingungen zur Verfügung, die im Verkaufskatalog abgedruckt waren. Im Anschluss an die Versteigerung wurde dem Käufer eine Zuschlagsbestätigung ausgehändigt, worin er mit seiner Unterschrift die Auktionsbedingungen der Verkäuferin als bindend anerkannt hat. A.b Mit E-Mail vom 8. Mai 2009 teilte die Y._ Ltd., die für die Verkäuferin die Zollabwicklungen macht, dem Käufer mit, dass sich der Lancia in temporärer Einfuhr in der Schweiz befinde und bei Wiedereinreise in die EU einfuhrsteuerpflichtig sei. In der Folge schaltete der Käufer einen Zollexperten ein und teilte der Verkäuferin mit E-Mail vom 7. August 2009 mit, dass Zoll und Steuern bei der Wiedereinfuhr des Fahrzeuges in die EU 29 % des Erwerbspreises zuzüglich Abwicklungskosten betrage, weshalb er die Rückabwicklung des Geschäfts sowie die Rücküberweisung des Kaufpreises wolle. A.c Das Fahrzeug wurde vom Käufer bei der Verkäuferin nie abgeholt und befindet sich seit dem 12. Dezember 2011 in einer vom Käufer gemieteten Garage in I._. B. B.a Am 2. Februar 2010 reichte der Käufer beim damaligen Gerichtskreis IX Schwarzenburg-Seftigen Klage gegen die Verkäuferin ein mit dem Begehren, diese sei zu verpflichten, ihm den Betrag von Fr. 44'800.-- nebst Zins seit dem 1. Oktober 2009 zu bezahlen. Die Verkäuferin verlangte widerklageweise, der Käufer sei zu verurteilen, ihr einen Betrag von Fr. 10'401.85 zuzüglich der seit der Klageeinreichung bis zur Urteilsfällung anfallenden Lagergebühr von Fr. 15.-- pro Tag zuzüglich MwSt und Zins seit wann rechtens zu bezahlen. Mit Entscheid vom 31. August 2011 wies das Regionalgericht Bern-Mittelland die Klage ab und verurteilte den Kläger in teilweiser Gutheissung der Widerklage, der Beklagten einen Betrag von Fr. 3'486.25 nebst Zins zu 5 % seit dem 9. April 2010 sowie einen Betrag von Fr. 8'102.30 nebst 5 % Zins seit dem 20. Dezember 2010 zu bezahlen. B.b Gegen dieses Urteil erhob der Kläger am 3. Oktober 2011 Berufung an das Obergericht des Kantons Bern. Die Beklagte erhob am 14. November 2011 Anschlussberufung. Mit Entscheid vom 9. Mai 2012 wies auch das Obergericht die Klage ab und verurteilte den Kläger in teilweiser Gutheissung der Widerklage, der Beklagten einen Betrag von Fr. 3'486.25 nebst Zins zu 5 % seit dem 9. April 2010 sowie einen Betrag von Fr. 9'926.10 nebst Zins zu 5 % seit dem 8. Februar 2011 zu bezahlen. C. Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht, der Entscheid des Obergerichts des Kantons Bern vom 9. Mai 2012 sei aufzuheben und die Klage gutzuheissen. Weiter sei die Beklagte zu verpflichten, dem Kläger Fr. 100.-- pro angebrochenen Monat ab 1. Dezember 2011 bis drei Monate nach Abholung des streitgegenständlichen Fahrzeugs durch die Beklagte nebst Zins zu 5 % ab mittlerem Verfall zu bezahlen. Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. Der Beschwerdeführer hat unaufgefordert eine Replik eingereicht. 