Sachverhalt: A. Die X._ AG, welche die Beschaffung von Informationen, insbesondere von gerichtsverwertbarem Beweismaterial, bezweckt, machte am 4. November 2010 vor dem Richteramt Dorneck-Thierstein Klage gegen A._ anhängig. Sie verlangte, dieser sei zu verurteilen, ihr die in Betreibung gesetzte Forderung in der Höhe von Fr. 39'445.75 zuzüglich Zins zu 5 % seit dem 15. Dezember 2009 zu bezahlen, und es sei der Rechtsvorschlag in der von ihr eingeleiteten Betreibung zu beseitigen. Zur Begründung brachte sie vor, der Auftraggeber A._ schulde ihr (der Beauftragten) eine Vergütung in entsprechender Höhe. A._ habe sie seit über zehn Jahren regelmässig in mündlicher Form mit Dienstleistungen (Ermittlungen, Recherchen, Wirtschaftsinformationen) beauftragt. Im Winter 2006 habe sie wiederum einen entsprechenden Auftrag erhalten und im Januar 2007 abgeschlossen. Ein weiterer Auftrag sei im Juni 2007 erteilt worden, und ein dritter Auftrag habe Abklärungen in Düsseldorf Ende Oktober 2007 beinhaltet. Nachdem A._ am 15. August 2007 eine Teilzahlung von Fr. 5'199.50 (nach Abzug der Kreditkartengebühr von 3 %) geleistet habe, verbleibe ein Restbetrag von Fr. 39'445.75 zu ihren Gunsten. A._ anerkannte im kantonalen Verfahren, dass er der X._ AG im Dezember 2006 einen Auftrag betreffend eine Observation erteilt habe, machte jedoch geltend, dafür sei ein Pauschalhonorar von Fr. 5'000.-- vereinbart worden, das er mit seiner Zahlung beglichen habe. Das Amtsgericht hiess die Klage mit Urteil vom 20. Dezember 2011 gut (Dispositiv-Ziffer 1) und beseitigte den Rechtsvorschlag in der von der X._ AG eingeleiteten Betreibung (Dispositiv-Ziffer 2). Dagegen erhob A._ Berufung an das Obergericht des Kantons Solothurn, das die Dispositiv-Ziffer 2 des erstinstanzlichen Urteils (betreffend die Beseitigung des Rechtsvorschlags) aufhob und die Berufung im Übrigen abwies. B. A._ (Beschwerdeführer) beantragt mit Beschwerde in Zivilsachen, das Urteil des Obergerichts sei aufzuheben, und die Klage sei vollumfänglich abzuweisen, eventualiter sei die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. Die X._ AG (Beschwerdegegnerin) begehrt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Vorinstanz schliesst auf Abweisung der Beschwerde, unter Verzicht auf eine Vernehmlassung. Mit Verfügung vom 31. August 2012 wurde das Gesuch des Beschwerdeführers um Gewährung der aufschiebenden Wirkung abgewiesen.