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.

Erwägungen:
1. Das angefochtene Urteil des Obergerichts ist ein verfahrensabschliessender Endentscheid (<ref-law>) einer letzten kantonalen Instanz (<ref-law>). Sodann übersteigt der Streitwert von Fr. 39'445.75 die Grenze nach <ref-law>. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist - unter Vorbehalt einer hinlänglichen Begründung (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG) - auf die Beschwerde einzutreten.
2. 2.1 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.5). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>).
Der Beschwerdeführer, der die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (vgl. <ref-ruling> E. 1.2; <ref-ruling> E. 2.2.2; <ref-ruling> E. 1.4.3).
2.2 Zu beachten ist, dass das Bundesgericht in die Beweiswürdigung des Sachgerichts nur eingreift, wenn diese willkürlich ist. Willkür liegt nicht schon dann vor, wenn eine andere Lösung ebenfalls in Betracht zu ziehen oder gar vorzuziehen wäre, sondern nur, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 5.1; <ref-ruling> E. 4.1; <ref-ruling> E. 2.1). Die Beweiswürdigung ist mithin nicht schon dann willkürlich, wenn sie nicht mit der Darstellung des Beschwerdeführers übereinstimmt, sondern bloss, wenn sie offensichtlich unhaltbar ist (<ref-ruling> E. 4.2.1; <ref-ruling> E. 2.1 S. 9; <ref-ruling> E. 2b). Dies ist insbesondere dann der Fall, wenn das Sachgericht offensichtlich unhaltbare Schlüsse zieht, erhebliche Beweise übersieht oder solche willkürlich ausser Acht lässt (vgl. BGE <ref-ruling> E. 2.1; <ref-ruling> E. 4b). Inwiefern die Beweiswürdigung willkürlich sein soll, ist in der Beschwerde klar und detailliert aufzuzeigen (<ref-ruling> E. 2.2; <ref-ruling> E. 1.3). Namentlich genügt es nicht, einzelne Beweise anzuführen, die anders als im angefochtenen Entscheid gewichtet werden sollen, und dem Bundesgericht in appellatorischer Kritik die eigene Auffassung zu unterbreiten, als ob diesem freie Sachverhaltsprüfung zukäme (vgl. BGE <ref-ruling> E. 2b).
3. Der Beschwerdeführer kritisiert die Sachverhaltsfeststellung der Vorinstanz mit Bezug auf die Höhe des Vergütungsanspruchs der Beschwerdegegnerin. Er moniert, die Vorinstanz sei aufgrund von offensichtlich unrichtigen Feststellungen zur Ansicht gelangt, dass die Beschwerdegegnerin den "Nachweis für die Honorarabsprache, die Art der Vergütung und die Angemessenheit der Honorarforderung" erbracht habe.
3.1 Die Höhe der Vergütung, die der Auftraggeber dem Beauftragten schuldet, bestimmt sich in erster Linie nach der Parteivereinbarung (<ref-ruling> E. 2.2 S. 261; <ref-ruling> E. 2 S. 111). Mithin war im kantonalen Verfahren durch Vertragsauslegung zu eruieren, ob sich die streitgegenständliche Honorarforderung in der Höhe von Fr. 39'445.75 auf eine entsprechende Parteivereinbarung abstützen lässt.
Die Vorinstanz prüfte folglich zu Recht, ob sich die Parteien bei Auftragserteilung über die Art und Höhe der Vergütung geeinigt haben. Zu diesem Zweck ging sie im Einzelnen auf die Parteibehauptungen ein und erstellte den rechtserheblichen Sachverhalt aufgrund verschiedener Beweise und Indizien, so namentlich der Zeugenaussage von B._, einer früheren Rechnung des "Büro B._" und dem Verhalten des Beschwerdeführers nach Rechnungsstellung am 6. Dezember 2007 und in der darauffolgenden Zeit bis zum Beginn der Rechtsstreitigkeit. Im Einzelnen befand sie, die Behauptung des Beschwerdeführers, dass er sich mit der Beschwerdegegnerin auf ein Pauschalhonorar in der Höhe von Fr. 5'000.-- geeinigt habe, sei nicht glaubhaft. Sie kam zum Schluss, die von der Beschwerdegegnerin geltend gemachten Stundenansätze in der Höhe von Fr. 126.-- und Fr. 158.-- respektive Fr. 185.-- seien dem Beschwerdeführer ebenso bekannt gewesen wie der Umstand, dass bei derartigen Ermittlungen erhebliche Spesen anfallen, hielt es also für erwiesen, dass sich die Parteien über die Abrechnung der Arbeit nach dem Zeitaufwand gemäss den entsprechenden Tarifen geeinigt hatten. Des Weiteren befand sie, dass sich sämtliche Operationen der Beschwerdegegnerin, sowohl bezogen auf den Grundsatz als auch auf die Art der Ausführung, im Rahmen des durch den Beschwerdeführer erteilten Auftrags bewegt hätten, stellte also das Vorliegen einer Parteivereinbarung fest, welche die Leistungen der Beschwerdegegnerin abdeckt.
Zusammengefasst stellte die Vorinstanz einen übereinstimmenden wirklichen Parteiwillen, d.h. einen natürlichen Konsens im Sinne von <ref-law> mit Bezug auf den Auftragsinhalt, die Vergütungsart sowie die Vergütungshöhe fest, woraus sie in rechtlicher Hinsicht folgerte, die von der Beschwerdegegnerin geltend gemachte Honorarforderung in der Höhe von Fr. 39'445.75 sei ausgewiesen.
3.2 Die Feststellung des übereinstimmenden wirklichen Parteiwillens nach <ref-law> beschlägt eine Tatfrage (vgl. <ref-ruling> E. 3.2). Die erwähnten Feststellungen der Vorinstanz binden das Bundesgericht somit in dem Masse, als sie nicht offensichtlich unrichtig sind und nicht auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (Erwägung 2.1). Einen solchen Mangel vermag der Beschwerdeführer nicht darzutun, soweit seine Ausführungen angesichts ihrer weitgehend appellatorischen Natur überhaupt zu hören sind. Es gelingt ihm insbesondere nicht, die Beweiswürdigung der Vorinstanz als willkürlich auszuweisen (Erwägung 2.2):
3.2.1 Er kritisiert die Auffassung der Vorinstanz, wonach er bis zur Einleitung des Gerichtsverfahrens nie geltend gemacht habe, die von der Beschwerdegegnerin erbrachten Leistungen seien über den erteilten Auftrag hinausgegangen, namentlich nicht nach Rechnungsstellung und Zustellung der Arbeitsrapporte am 6. Dezember 2007. Er meint, es sei aktenwidrig und offensichtlich unrichtig, wenn die Vorinstanz gestützt auf die unterbliebene Beanstandung zur Ansicht gelangt sei, dass er "die Leistungen der Beschwerdegegnerin vorbehaltlos entgegen genommen" habe. Diese Auffassung werde widerlegt durch den Umstand, dass er die Rechnung auch nach mehrfacher Mahnung nicht bezahlt, gegen die Betreibung umgehend Rechtsvorschlag erhoben und seit Beginn der rechtlichen Auseinandersetzung jeweils vehement die Höhe der Forderung bestritten habe.
Dabei verkennt der Beschwerdeführer, dass die Vorinstanz die unterbliebene Beanstandung der Rechnung nicht als rechtsgeschäftliche Anerkennung der Pflicht zur Zahlung eines bestimmten Honorars wertete. Vielmehr würdigte sie sein Verhalten nach Erhalt der Rechnung und der Arbeitsrapporte bloss als Indiz dafür, dass sich die in Rechnung gestellten Leistungen im Rahmen des erteilten Auftrags hielten sowie weiter dafür, dass dem Beschwerdeführer die von der Beschwerdegegnerin geltend gemachten Stundenansätze bekannt waren, berücksichtigte es mit anderen Worten in der Beweiswürdigung betreffend tatsächliche Willensübereinstimmung bei Vertragsschluss zusammen mit weiteren Umständen. Dies ist denn unter Willkürgesichtspunkten auch nicht zu beanstanden: Es erscheint in der Tat nur schwer verständlich, weshalb der Beschwerdeführer die Rechnung ohne ausdrückliche Beanstandung hingenommen haben soll, wenn er der Auffassung gewesen sein will, die darin abgerechneten Leistungen seien über den erteilten Auftrag hinausgegangen respektive er habe mit der Beschwerdegegnerin ein Pauschalhonorar vereinbart. Es ist entgegen der Auffassung des Beschwerdeführers auch ohne Weiteres nachvollziehbar, wenn die Vorinstanz das Nichtbezahlen der Rechnung nicht mit einer ausdrücklichen Beanstandung der Leistungen gleichsetzte, kann solches Verhalten des Schuldners doch auch andere Gründe haben.
3.2.2 Weiter hält der Beschwerdeführer die vorinstanzlichen Ausführungen zur Vereinbarung des Stundenansatzes und der Spesen der Beschwerdegegnerin für offensichtlich unrichtig. Indessen lässt er hierzu eine genügend begründete Willkürrüge vermissen: In seinen Ausführungen, die alle dahingehen, dass ihm die Stundenansätze nicht bekannt gewesen seien, beschränkt er sich darauf, den vorinstanzlichen Erwägungen eigene Behauptungen und Würdigungen entgegenzuhalten, so etwa, es sei "doch sehr unwahrscheinlich, dass dem Beschwerdeführer die Beträge, die ihm im Rahmen eines mehrere Jahre zurückliegenden Auftragsverhältnisses (dessen Existenz nicht erwiesen ist) in Rechnung gestellt wurden, noch immer bekannt" seien. Damit gelingt es dem Beschwerdeführer nicht einmal im Ansatz, seinen Willkürvorwurf gegenüber der Vorinstanz zu begründen (vgl. Erwägung 2.2). Bei der vorinstanzlichen Feststellung hat es somit ohne Weiteres sein Bewenden.
4. Weiter rügt der Beschwerdeführer, die Vorinstanz habe die <ref-law> verletzt, indem sie verkannt habe, dass seine Erklärung in Ziffer 1 des mit "Schuldanerkennung" betitelten Dokuments vom 11./15. Dezember 2009 unter einer Suspensivbedingung gestanden habe. Auch diese Rüge verfängt nicht:
Das fragliche Schriftstück hat den folgenden Wortlaut:
"1. A._ schuldet der Firma X._ AG, den Betrag von CHF 39'445.75.
2. Wird die Schuld in einem Betrag (CHF) beglichen, so reduziert sie sich auf den vereinbarten Betrag von CHF 27'000.00.
3. Die Schuld kann auch mit einer WIR-Geld Zahlung von CHF 39'445.75 bezahlt werden.
4. Der Betrag ist bis spätestens Ende Februar 2010 zu begleichen.
5. Die Firma X._ AG zieht per sofort die gegen A._ erhobene Betreibung zurück und veranlasst deren Löschung im Betreibungsregister Dornach."
Der Beschwerdeführer scheint sich zunächst gegen die Qualifikation der Schuldanerkennung als Rechtsöffnungstitel im Sinne von <ref-law> zu wenden, worauf es im vorliegenden ordentlichen Klageverfahren indessen von vornherein nicht ankommt.
Die Rüge, die Schuldanerkennung des Beschwerdeführers habe unter der (nicht eingetretenen) Suspensivbedingung gestanden, dass die Beschwerdegegnerin ihre Betreibung zurückzieht, verfehlt aber auch im Übrigen ihr Ziel: Ob die Erklärung des Beschwerdeführers, dass er der Beschwerdegegnerin den Betrag von Fr. 39'445.75 schulde, an eine aufschiebende Bedingung im Sinne der <ref-law> geknüpft war, könnte von vornherein nur dann von Bedeutung sein, wenn eine rechtsgeschäftliche Wirkung der Äusserung zur Diskussion stünde, so namentlich, wenn die Vorinstanz geschlossen hätte, sie stelle ein Schuldbekenntnis im Sinne von <ref-law> dar, das eine Beweislastumkehr zu Ungunsten des Beschwerdeführers nach sich ziehe (vgl. <ref-ruling> E. 3.2 S. 273; <ref-ruling> E. 4a S. 564). Dies ist aber vorliegend nicht der Fall: Die Vorinstanz nahm vielmehr beweiswürdigend an, Ziffer 1 des Dokuments sei geeignet, zusammen mit den weiteren Hinweisen die Existenz der anerkannten Forderung nachzuweisen, zog sie also bei der Ermittlung des Vertragsinhalts gemäss Parteivereinbarung in Betracht. Sie stützte nämlich ihre tatsächlichen Feststellungen bezüglich Auftragsinhalt, Vergütungsart sowie Vergütungshöhe (vgl. Erwägung 3) unter anderem auf diese Erklärung des Beschwerdeführers. Da die Vorinstanz in diesen Punkten durchwegs zu einem positiven Beweisergebnis gelangt ist, erweist sich die Frage nach einer durch ein Schuldbekenntnis bewirkten Beweislastumkehr als gegenstandslos (vgl. <ref-ruling> E. 4.3.4; <ref-ruling> E. 5.4 S. 602), und die Rüge einer Verletzung der <ref-law> entbehrt der Grundlage.
Der Vollständigkeit halber ist schliesslich zu erwähnen, dass die genannte beweiswürdigende Berücksichtigung der Schuldanerkennung durch die Vorinstanz keineswegs willkürlich ist, wie der Beschwerdeführer ohne hinreichende Begründung zu unterstellen scheint. Selbst wenn die Schuldanerkennung des Beschwerdeführers als rechtsgeschäftliche Erklärung vom Rückzug der Betreibung durch die Beschwerdegegnerin abhängig gewesen sein sollte - wofür sich notabene im Text der Erklärung keinerlei Anhaltspunkte finden - ist sie mit Bezug auf die Beweiswürdigung betreffend das von den Parteien bei Vertragsabschluss tatsächlich Gewollte keineswegs obsolet oder unbeachtlich, wie der Beschwerdeführer meint. Vielmehr bietet bereits der blosse Umstand, dass der Beschwerdeführer die entsprechende Erklärung überhaupt abgegeben hat, ein Indiz für das Vorliegen der von der Beschwerdegegnerin behaupteten Vergütungsvereinbarung. Die Vorinstanz durfte diesen Umstand in die Beweiswürdigung einbeziehen, ohne sich dadurch dem Vorwurf der willkürlichen Sachverhaltsfeststellung auszusetzen.
5. Die Beschwerde ist nach dem Gesagten abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

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