Sachverhalt:
A. Am 16./17. April 2007 schloss die Stadt Y._ als Bauherrin mit A._ (Beschwerdeführer, Kläger) einen Planervertrag betreffend das Sanierungsprojekt Z._ wobei sie ihm die Fachplanung der Rutschbahnanlage, der Beckensanierung und des Energiedachs übertrug. In der Folge beauftragte die Stadt Y._ die X._ AG (Beschwerdegegnerin, Beklagte) als Totalunternehmerin mit der Ausführung des Projekts.
Am 22. August 2007 offerierte der Beschwerdeführer der Beschwerdegegnerin die Ausführungsplanung für die Bäder- und Sanitärtechnik, Duschen und Energiedach sowie die Fachbauleitung und Baubegleitung inklusive Überwachung der Schlussabnahmen und Beratung bei der Inbetriebnahme. Diese Offerte nahm die Beschwerdegegnerin an.
Am 19. Januar 2008 stellte der Beschwerdeführer der Beschwerdegegnerin Rechnung in der Höhe von Fr. 45'207.40, worauf die Beschwerdegegnerin eine Teilzahlung von Fr. 30'000.-- erbrachte. Am 11. März 2008 folgte eine Rechnung des Beschwerdeführers über Fr. 39'662.70, worin der Restbetrag gemäss Abrechnung vom 19. Januar 2008 enthalten war, und am 3. April 2008 eine weitere Rechnung über Fr. 3'928.70. Alsdann liess der Beschwerdeführer die Beschwerdegegnerin für die ausstehenden Beträge von Fr. 39'662.70 sowie Fr. 3'928.70 nebst Zins betreiben, worauf diese Rechtsvorschlag erhob.
Daraufhin liess der Beschwerdeführer auf dem Grundstück Nr. B. Z._ im Grundbuch Y._ ein Bauhandwerkerpfandrecht im Betrag von Fr. 43'591.40 nebst Zins zu 8 % seit 29. Mai 2008 vorläufig eintragen.
B. Am 6. Mai 2008 erhob der Beschwerdeführer Klage gegen die Beschwerdegegnerin. Er beantragte vor dem Kantonsgericht Schaffhausen, die Beschwerdegegnerin sei zu verpflichten, ihm Fr. 43'591.40 zuzüglich Zins zu bezahlen (Ziff. 1) und es sei der Rechtsvorschlag zu beseitigen sowie ihr in dieser Höhe der Forderung definitive Rechtsöffnung zu erteilen (Ziff. 2) und der Beschwerdegegnerin seien die Kosten, u.a. für die provisorische Eintragung des Bauhandwerkerpfandrechts, aufzuerlegen (Ziff. 3). Das Kantonsgericht wies die Klage am 14. Dezember 2009 ab.
Der Beschwerdeführer appellierte an das Obergericht des Kantons Schaffhausen und beantragte Folgendes:
"1. Es seien die Ziff. 1 bis 3 des Urteils des Kantonsgerichts Schaffhausen vom 14. Dezember 2009 aufzuheben.
2. Es sei das Verfahren i.S.v. <ref-law> zur Ausfällung eines neuen Entscheids an das Kantonsgericht Schaffhausen zurückzuweisen, wonach
a) die Beklagte zu verpflichten sei, dem Kläger Fr. 43'591.40 zuzüglich Zins zu 8 % seit 29. April 2008, eventualiter zu 5 % seit 4. April 2008, zu bezahlen;
b) der von der Beklagten in der Betreibung Nr. 111._ des Betreibungsamtes Schaffhausen (Zahlungsbefehl vom 28. April 2008) erhobene Rechtsvorschlag zu beseitigen und dem Kläger gemäss Ziff. 1 hiervor definitive Rechtsöffnung zu erteilen sei;
c) die Kosten des Verfahrens betreffend Eintragung eines provisorischen Bauhandwerkerpfandrechts gemäss Verfügung des Vizepräsidenten des Bezirksgerichts Kreuzlingen vom 29. März 2008, Ziff. 3, von Fr. 250.-- sowie die Kosten des Friedensrichteramtes Y._ von Fr. 280.-- für den Sühnevorstand vom 26. August 2008 der Beklagten aufzuerlegen seien und es sei die Beklagte zu verpflichten, den Kläger für jene Verfahren angemessen, mindestens aber mit Fr. 1'500.-- zuzüglich 7,6 % MWST, zu entschädigen.
3. Eventualiter: Es sei für den Fall, dass das Verfahren nicht zur Ausfällung eines neuen Entscheids an das Kantonsgericht Schaffhausen zurückgewiesen wird
a) die Beklagte zu verpflichten, dem Kläger Fr. 43'591.40 zuzüglich Zins zu 8 % seit 29. April 2008, eventualiter zu 5 % seit 4. April 2008, zu bezahlen;"
[es folgt eine Wiederholung der Lit. b-c von Ziff. 2 und
4. Kosten- und Entschädigungsfolgen].
Mit Urteil vom 4. Februar 2011 wies das Obergericht die Berufung und die Klage ab.
C. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, das Urteil des Obergerichts aufzuheben und das Verfahren zur Ausfällung eines neuen Entscheids an das Kantonsgericht, eventualiter an das Obergericht zurückzuweisen, wobei diese wiederum gemäss den vorinstanzlichen Rechtsbegehren Ziff. 2 lit. a-c zu entscheiden hätten; eventualiter habe das Bundesgericht selbst im Sinne der vorgenannten vorinstanzlichen Rechtsbegehren zu entscheiden.
Die Beschwerdegegnerin beantragt, die Beschwerde vollumfänglich abzuweisen. Die Vorinstanz verzichtete auf Vernehmlassung.

Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Endentscheid (<ref-law>; <ref-law>). Es geht um eine Zivilsache (<ref-law>) mit einem Streitwert von über Fr. 30'000.-- (<ref-law>). Unter Vorbehalt zulässiger Rügen und einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 und 106 Abs. 2 BGG) ist auf die Beschwerde einzutreten.
2. 2.1 Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft solche Rügen nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law>; vgl. <ref-ruling> E. 1.3.1; <ref-ruling> E. 2.2; <ref-ruling> E. 3.2 S. 444 f.).
Macht der Beschwerdeführer eine Verletzung des Willkürverbots von <ref-law> geltend, genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich. Er hat vielmehr im Einzelnen aufzuzeigen, inwiefern dieser offensichtlich unhaltbar ist (<ref-ruling> E. 4.3 S. 522; <ref-ruling> E. 3 S. 352). Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffend erscheint, genügt nicht (<ref-ruling> E. 4.2; <ref-ruling> E. 3.1 S. 153; <ref-ruling> E. 3.1).
2.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, 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).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, kann sich nicht damit begnügen, den bestrittenen Feststellungen eigene tatsächliche Behauptungen gegenüberzustellen oder darzulegen, wie die Beweise seiner Ansicht nach zu würdigen gewesen wären. Vielmehr hat er klar und substantiiert aufzuzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (vgl. <ref-ruling> E. 1.4.3; <ref-ruling> E. 7.1). Soweit der Beschwerdeführer den Sachverhalt ergänzen will, hat er zudem mit Aktenhinweisen darzulegen, dass er entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (Urteile 4A_214/2008 vom 9. Juli 2008 E. 1.2, nicht publ. in: <ref-ruling>; 4A_470/2009 vom 18. Februar 2010 E. 1.2).
In der Beschwerde ist überdies darzutun, inwiefern die Behebung des gerügten Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 2.2.2).
Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (<ref-ruling> E. 1.4.3), ebenso wenig auf Vorbringen, die in den tatsächlichen Feststellungen der Vorinstanz keine Stütze finden, ohne dass dazu eine taugliche Sachverhaltsrüge im vorstehenden Sinne substantiiert wird, oder auf Rügen, die auf solchen Vorbringen aufbauen.
3. Die Vorinstanz stellte fest, dass der Vertrag, den die Parteien gemäss Offerte des Beschwerdeführers vom 22. August 2007 geschlossen haben, sich in drei Teile gliederte:
- Ausführungsplanung für Bädertechnik mit einem "Kostendach ca. exkl. MWST" von Fr. 12'000.--,
- Ausführungsplanung für Sanitärtechnik, Duschen und Energiedach mit "Kostendach ca. exkl. MWST" von Fr. 16'500.--,
- Fachbauleitung und Baubegleitung inkl. Überwachung der Schlussabnahme und Beratung bei der Inbetriebnahme mit "Kostendach Bauleitung [...] ca. exkl. MWST" von Fr. 9'200.--.
Die Beschwerdegegnerin habe für ausgeführte Arbeiten Fr. 30'000.-- bezahlt. Am 4. April 2008 habe der Beschwerdeführer wegen ausbleibender Zahlungen seine Arbeiten für die Beschwerdegegnerin eingestellt. Der Beschwerdeführer fordere von der Beschwerdegegnerin in der Hauptsache den Betrag von Fr. 43'591.40 nebst Zins. Er begründe dies zum einen damit, dass er für die Beschwerdegegnerin die Arbeiten gemäss Offerte vom 22. August 2007 geleistet habe. Zum andern sei er von der Beschwerdegegnerin laufend mit Zusatzarbeiten beauftragt worden.
Das Kantonsgericht gelangte zusammenfassend zum Schluss, der Beschwerdeführer habe den rechtserheblichen Sachverhalt weder in Bezug auf das Zustandekommen und den Inhalt von Zusatz- und Ergänzungsaufträgen noch bezüglich Zuordnung seiner Aufwendungen und Leistungen zum Grundvertrag gemäss Offerte vom 22. August 2007 sowie zu den behaupteten Zusatz- und Ergänzungsaufträgen ausreichend substantiiert. Die Vorinstanz teilte diese Auffassung vollumfänglich. Was der Beschwerdeführer dagegen einwendet, verfängt nicht:
4. 4.1 Er beanstandet zunächst, das Kantonsgericht habe es unterlassen, ihn anlässlich der Hauptverhandlung zu einem zweiten mündlichen Vortrag zuzulassen, und das Obergericht habe dies nicht sanktioniert. Die Verweigerung eines zweiten mündlichen Vortrags stehe in offensichtlichem Widerspruch zu Art. 171 aZPO/SH und bedeute im Vergleich zu anderen Prozessparteien eine ungleiche Behandlung (<ref-law>). Indem das Kantonsgericht und mit ihm das Obergericht eine unzureichende Substantiierung angenommen habe, ihm gleichzeitig aber die Möglichkeit einer Replik verweigert worden sei, verletze das Obergericht das rechtliche Gehör (<ref-law>) und überdies die Grundsätze von Treu und Glauben (<ref-law>) und der Verfahrensfairness (Art. 6 Ziff. 1 EMRK).
4.2 Nach Art. 171 Abs. 1 der vorliegend noch anwendbaren Zivilprozessordnung des Kantons Schaffhausen (aZPO/SH) stehen jeder Partei in der Hauptverhandlung "in der Regel" zwei Vorträge zu. Die Vorinstanz führte dazu aus, der erste Vortrag diene der Ergänzung der Klagebegründung bzw. der Klageantwort. Im zweiten Vortrag könne der Kläger zur Klageantwort Stellung nehmen und der Beklagte könne duplizieren. Vorliegend habe es sich jedoch so verhalten, dass der Beschwerdeführer in einem einzigen Vortrag sowohl seine Klagebegründung ergänzt als auch zur Klageantwort der Beschwerdegegnerin Stellung genommen habe. Die Beschwerdegegnerin habe sich daraufhin zu den Ausführungen des Klägers vernehmen lassen. In dieser Situation hätte den Parteien lediglich dann ein weiterer Vortrag (Triplik und Quadruplik) gewährt werden müssen, wenn neue Behauptungen und Bestreitungen vorgebracht worden wären. Dass dies der Fall gewesen sei, mache der Kläger nicht geltend und sei auch nicht ersichtlich, weshalb eine Gehörsverletzung zu verneinen sei.
4.3 Ein offensichtlicher Widerspruch zum Wortlaut von Art. 171 Abs. 1 aZPO/SH liegt nicht vor, nachdem diese Bestimmung den Parteien "in der Regel" einen zweiten Vortrag zugesteht, mithin eine Replik nicht zwingend vorsieht.
Soweit der Beschwerdeführer in diesem Zusammenhang einen Widerspruch "zur langjährigen Praxis" und damit eine Ungleichbehandlung geltend macht, ist dem zu entgegnen, dass er nicht darlegt, dass er die hier angebotenen Zeugeneinvernahmen diverser Schaffhauser Anwaltskollegen bereits vorinstanzlich vorgebracht hat. Damit handelt es sich um neue Beweismittel im Sinne von <ref-law>, die ohne Weiteres schon vor Obergericht hätten vorgebracht werden können, und mit denen der Beschwerdeführer deshalb vor Bundesgericht nicht zu hören ist. Ohnehin legt er nicht dar, dass die kantonalen Gerichte in einer gleichen Situation (Vortrag dient der Ergänzung der Klagebegründung sowie der Stellungnahme zur Klageantwort, keine neuen Behauptungen und Bestreitungen) den Parteien einen zweiten mündlichen Vortrag zugestehen. Von einer Ungleichbehandlung in gleicher Situation ist daher nicht auszugehen.
Der Beschwerdeführer vermag auch aus den Grundsätzen von Treu und Glauben und eines fairen Verfahrens nichts für sich abzuleiten. Die Beschwerdegegnerin hatte bereits in der Klageantwort ausgeführt, die Klage sei nicht substantiiert. Der Beschwerdeführer musste demnach spätestens ab Erhalt der Klageantwort wissen, dass ihm mangelnde Substantiierung vorgeworfen wird. An der Hauptverhandlung hätte er diese nachholen können. Sein erster mündlicher Vortrag hätte ihm dazu hinreichend Gelegenheit geboten, dient dieser dem Kläger doch namentlich dazu, seine Behauptungen im Hinblick auf die in der Klageantwort erhobenen Bestreitungen weiter zu substantiieren (ANNETTE DOLGE, Der Zivilprozess im Kanton Schaffhausen im erstinstanzlichen ordentlichen Verfahren, 2001, S. 118). Es trifft daher nicht zu, dass ihm durch die Nichtgewährung eines zweiten mündlichen Vortrags die Möglichkeit genommen wurde, den Vorwurf mangelnder Substantiierung zu parieren bzw. diese nachzuholen. Von einem Verstoss gegen Treu und Glauben oder gegen die Verfahrensfairness kann daher keine Rede sein.
Schliesslich ist noch festzuhalten, dass der Beschwerdeführer nicht geltend macht, an der Hauptverhandlung verlangt zu haben, zu einem zweiten Vortrag zugelassen zu werden. Es wurde ihm also nichts verweigert, worum er ersucht hätte. Wie aus der Beschwerde hervorgeht, hätte er - nun im Nachhinein betrachtet - den zweiten mündlichen Vortrag nutzen wollen, um die mangelnde Substantiierung seiner Klage nachzuholen und nicht etwa, um auf neue Vorbringen der Beschwerdegegnerin zu replizieren. Wie gesagt, hätte er dazu aber im ersten mündlichen Vortrag Gelegenheit gehabt. Es ist daher auch keine Gehörsverletzung gegeben.
5. 5.1 Der Beschwerdeführer rügt weiter eine willkürliche Anwendung bzw. eine Nichtanwendung vom Art. 174 aZPO/SH über die richterliche Fragepflicht. Das Kantonsgericht habe es unterlassen, ihm Fragen zum Grundvertrag und den Zusatzaufträgen zu stellen bzw. ihm eventuell Substantiierungshinweise zu geben, soweit seine Vorbringen unklar, unvollständig oder unbestimmt gewesen sein sollten. Das Obergericht sei seiner diesbezüglichen Beanstandung nicht gefolgt, womit sein rechtliches Gehör verletzt sei.
5.2 Die Vorinstanz führte aus, im Gegensatz zu den Gerichten im Kanton Zürich würden die Schaffhauser Gerichte den Parteien praxisgemäss keine Substantiierungshinweise geben. Zwar hätten sie im Rahmen der richterlichen Fragepflicht Unklarheiten und Unvollständigkeiten in den Ausführungen der Parteien zu beheben. Vorliegend seien die klägerischen Eingaben aber derart unsubstantiiert, dass dieser Mangel durch richterliche Fragen allein nicht behoben werden könne, zumal es nicht die Aufgabe des Gerichts sei, zwecks Substantiierung der einzelnen Forderungen die vom Kläger eingereichten Unterlagen zu durchsuchen. Im Übrigen sei der Beschwerdeführer bereits vor Kantonsgericht anwaltlich vertreten gewesen. Auch daher habe das Kantonsgericht ihn nicht erst auf die mangelhafte Substantiierung aufmerksam machen müssen. Von einem Anwalt dürfe aufgrund seiner besonderen Ausbildung und Zulassung vor Gericht erwartet werden, dass er in einem Forderungsprozess ohne Nachfragen des Richters in der Lage sei, die rechtserheblichen Tatsachen nicht nur in den Grundzügen, sondern so detailliert und präzise darzulegen, dass eine rechtliche Subsumtion möglich sei und über die rechtserheblichen Tatsachen Beweis abgenommen werden könne.
5.3 Nach Art. 174 Abs. 1 aZPO/SH ist der Richter dafür besorgt, dass die Vorträge der Parteien den gesetzlichen Vorschriften entsprechen; Mängel [der mündlichen Vorträge] sind durch geeignete Fragen zu beheben. Die richterliche Fragepflicht dient dazu, Unklarheiten, Unvollständigkeiten oder Unbestimmtheiten in den Ausführungen der Parteien zu beheben, wobei die Schwelle bei rechtskundig vertretenen Personen grundsätzlich höher angesetzt wird (DOLGE, a.a.O., S. 120).
5.4 Der Vorwurf willkürlicher Anwendung von Art. 174 aZPO/SH ist unbegründet. Da der Beschwerdeführer seit Verfahrensbeginn anwaltlich vertreten war, bestand keine Gefahr von Nachteilen wegen Rechtsunkenntnis, womit die Fragepflicht der Vorinstanz grundsätzlich eingeschränkt war. Zudem war der Sachverhalt nicht sehr kompliziert, weshalb die Fragepflicht auch nicht aus diesem Grund greifen musste. Im Gegenteil, unter Berücksichtigung der Tatsache, dass der Beschwerdeführer von der Beschwerdegegnerin bereits in der Klageantwort darauf aufmerksam gemacht worden war, dass er seine Forderung nicht genügend substantiiert hatte, bestand für das Gericht kein Grund zur Intervention, sei es die Parteien zu befragen oder Substantiierungshinweise anzubringen. Der Beschwerdeführer wusste vielmehr um seine Substantiierungspflicht und es wäre ihm ohne Weiteres möglich und zuzumuten gewesen, dieser nachzukommen. Der Beschwerdeführer verkennt, dass es nicht Sache des Richters ist, prozessuale Nachlässigkeiten auszugleichen. Dazu dient die richterliche Fragepflicht nicht (Urteile 4A_330/2010 vom 9. August 2010 E. 2.2; 4P.229/1999 vom 21. Dezember 1999 E. 1c).
5.5 Die Rüge einer Verletzung des rechtlichen Gehörs geht in diesem Zusammenhang ins Leere. Aus <ref-law> ergibt sich nicht eine Fragepflicht des Gerichts, wie der Beschwerdeführer sie in Art. 174 aZPO/SH zu erkennen glaubt. Der verfassungsmässige Minimalanspruch auf rechtliches Gehör vermittelt einer Prozesspartei keinen Anspruch auf Belehrung (Urteil 5A_180/2009 vom 19. Mai 2009 E. 2.2). Die Behörde hat den Rechtssuchenden nur anzuhören; sie muss ihn jedoch nicht inhaltlich darin instruieren, was er zur Durchsetzung seines Rechtsbegehrens vorzutragen hat. Unterliegt eine Zivilrechtsstreitigkeit - wie im vorliegenden Fall - der Dispositions- und Verhandlungsmaxime, so ist es vielmehr am Rechtssuchenden selbst, die Tatsachen zu behaupten und zu beweisen, aus deren Vorliegen er seinen Anspruch herleitet. Davon entbindet ihn der Gehörsanspruch nicht (Urteil 5A_458/2010 vom 9. September 2010 E. 4.2).
Ebenso wenig liegt eine Verletzung der aus dem Gehörsanspruch fliessenden Begründungspflicht der Behörden vor (dazu <ref-ruling> E. 2.2.1). Die Vorinstanz hat sich mit der Rüge des Beschwerdeführers betreffend richterliche Fragepflicht auseinandergesetzt und deren Abweisung mit einer nachvollziehbaren Begründung versehen.
6. 6.1 Schliesslich bestreitet der Beschwerdeführer, seine Forderung ungenügend substantiiert zu haben. Er habe die vertraglichen Beziehungen aufgezeigt und die zusätzlichen, ausserhalb des nach Massgabe der Offerte vom 22. August 2007 abgeschlossenen Werkvertrags erbrachten Arbeiten wie jene im Rahmen dieses Vertrags im Detail dargelegt. Ebenso seien die daraus resultierenden Forderungen im Quantitativ beziffert worden. Die Darstellung der Vorinstanz betreffend eine mangelnde Substantiierung sei entsprechend falsch, aktenwidrig und willkürlich.
6.2 Die Pflicht einer Prozesspartei, ihre Sachdarstellungen zu substantiieren, bedeutet, dass sie die Tatsachen nicht nur in den Grundzügen, sondern so umfassend und klar darzulegen hat, dass darüber Beweis abgenommen werden kann. Dabei bestimmt das Bundesrecht, wie weit ein Sachverhalt zu substantiieren ist, damit er unter die Bestimmungen des materiellen Rechts subsumiert werden kann (<ref-ruling> E. 2b S. 339; seither <ref-ruling> E. 3.3 S. 162; <ref-ruling> E. 2b S. 368; <ref-ruling> E. 3e S. 187 f.).
Die inhaltliche Tragweite der Substantiierungslast hängt auch vom prozessualen Verhalten der Gegenpartei ab. Tatsachenbehauptungen müssen so konkret formuliert sein, dass ein substantiiertes Bestreiten möglich ist oder der Gegenbeweis angetreten werden kann (vgl. <ref-ruling> E. 2 S. 113 f.). Bestreitet der Prozessgegner das an sich schlüssige Vorbringen der behauptungsbelasteten Partei, kann diese gezwungen sein, die rechtserheblichen Tatsachen nicht nur in den Grundzügen, sondern so umfassend und klar darzulegen, dass darüber Beweis abgenommen werden kann (BGE <ref-ruling> E. 2c; <ref-ruling> E. 3 S. 341). Stellt der kantonale Richter jedoch überhöhte Anforderungen an die Substantiierungslast, indem er detailliertere Tatsachenbehauptungen verlangt als für die rechtliche Beurteilung des anspruchsbegründenden Sachverhalts nötig ist, verletzt er Bundesrecht (<ref-ruling> E. 2a S. 291).
6.3 Wie schon das Kantonsgericht erachtete auch das Obergericht die klägerische Forderung weder betreffend den Grundvertrag noch der angeblichen Zusatzaufträge als hinlänglich substantiiert. Bezüglich des Grundvertrags gemäss Offerte vom 22. August 2007 habe es der Beschwerdeführer unterlassen, für jeden der drei Teile separat darzulegen, welche Arbeiten er wann im Einzelnen geleistet habe und was diese gekostet hätten. Noch weniger habe er die von ihm behaupteten Zusatzaufträge substantiiert. Er führe weder substantiiert aus, wann ihm die Beschwerdegegnerin welche zusätzlichen Aufträge erteilt habe, noch lege er dar, welche Arbeiten er wann für welchen Zusatzauftrag im Einzelnen geleistet habe und was diese gekostet hätten. Er erkläre auch nicht, wie sich die eingeklagte Forderung bezüglich der einzelnen Zusatzaufträge aufschlüssele. Der Verweis auf die eingereichten Unterlagen genüge nicht zur Substantiierung der eingeklagten Forderung.
6.4 Dass die Vorinstanz damit überhöhte Substantiierungsanforderungen gestellt und demnach Bundesrecht verletzt hätte, zeigt der Beschwerdeführer nicht auf. Er hält es für unerheblich, wann er die einzelnen Arbeiten ausgeführt habe. Das zeitliche Moment ist zwar nicht allein ausschlaggebend, es bildet aber eine der Komponenten, um die geleisteten Arbeiten, für die Rechnung gestellt wird, hinlänglich bestimmt zu konkretisieren, damit der Besteller prüfen kann, ob die fakturierten Arbeiten effektiv diejenigen sind, für die er Auftrag erteilt hat und die auch geleistet worden sind. Ohnehin beruht der Vorwurf mangelnder Substantiierung nicht einzig auf der Nichtangabe, wann die einzelnen Arbeiten ausgeführt wurden.
Es trifft auch nicht zu, wie der Beschwerdeführer behauptet, dass unbestritten geblieben sei, dass die Beschwerdegegnerin dem Beschwerdeführer die von ihm behaupteten Aufträge (mit Ausnahme der Werkstattplanung) erteilt habe und dass er sämtliche Arbeiten ausgeführt habe. Die Beschwerdegegnerin hatte im Gegenteil bestritten, dem Beschwerdeführer Zusatzaufträge erteilt zu haben (solche hätte allenfalls die Stadt Y._ erteilt und wären von ihr abzugelten). Sodann beanstandete sie insbesondere, dass der Beschwerdeführer in seiner Rechnung vom 19. Januar 2008 alles durcheinander gemischt habe, ohne Rücksicht auf die vertraglichen Grundlagen. Die Arbeiten aus dem Grundvertrag hätten aufgeschlüsselt werden müssen, um prüfen zu können, ob das Kostendach eingehalten wurde. Weiter bemängelte sie konkret in Bezug auf die aufgeschlüsselte Rechnung vom 16. April 2008, dass diese Arbeiten umfasse, die auf dem Vertrag mit der Stadt Y._ beruhten. Auch bestritt sie, die Werkstattplanung in Auftrag gegeben zu haben. Zudem habe der Beschwerdeführer seine Arbeiten aus dem Grundvertrag gemäss Offerte vom 22. August 2007 vorzeitig abgebrochen und somit nicht die vollen Leistungen erbracht, weshalb sie über die bezahlten Fr. 30'000.-- hinaus nichts schulde. Ebenso deckte die Beschwerdegegnerin auf, dass die Auflistung in der Klageschrift nicht mehr mit derjenigen vom 16. April 2008 übereinstimme.
Namentlich angesichts dieser Bestreitungen der Beschwerdegegnerin durfte das Kantonsgericht und mit ihm die Vorinstanz verlangen, dass der Beschwerdeführer nicht nur die einzelnen Arbeiten auflistete, sondern die behaupteten Aufwendungen konkretisierte und in zeitlicher und sachlicher Hinsicht den drei Teilen gemäss Offerte vom 22. August 2007 zuordnete sowie die dafür entfallenden Honorarbeträge nannte, damit überprüft werden konnte, ob die für die drei Teile vereinbarten Kostendächer eingehalten wurden. Dies tat er jedoch nach den Feststellungen im angefochtenen Urteil nicht. Die Vorinstanz hielt zutreffend fest, dass es nicht Aufgabe des Gerichts ist, selbst in den im Recht liegenden Materialien jene Unterlagen herauszusuchen, welche die eingeklagte Forderung in Bezug auf den Grundvertrag substantiieren könnten. Es nützt dem Beschwerdeführer nichts, wenn er in der Beschwerde behauptet, diese Unterlagen seien nicht kommentarlos eingereicht worden. Er habe in der Klagebegründung (S. 13a - 14, act. 37 f.) in einer übersichtlichen Tabelle seine gesamten Aufwendungen aufgelistet und auf den folgenden Seiten im Detail erläutert. Denn die genannte Tabelle präsentiert sich als blosse Arbeitszeiterfassung. Daraus ist jedoch nicht ersichtlich, welche Arbeiten zu welchem Preis auf die einzelnen Teile des Grundvertrages gemäss Offerte vom 22. August 2007 entfallen. Ebenso wenig wird dies auf den folgenden Seiten der Klagebegründung erklärt. Dass die Vorinstanz in den dortigen Ausführungen keine hinlängliche Substantiierung im verlangten Sinne erblicken konnte, ist nicht zu beanstanden.
Die Vorinstanz stellte auch bezüglich der Zusatzaufträge keine überhöhten Substantiierungsanforderungen. So war es bei der genannten Bestreitungslage in der Tat unabdingbar, dass der Beschwerdeführer die von ihm behaupteten Zusatzaufträge separat dem Bestande und dem Inhalt nach substantiierte und namentlich belegte, dass diese ihm effektiv von der Beschwerdegegnerin erteilt worden waren. Auch durfte verlangt werden, dass er konkret darlegte, welche Arbeiten er für die einzelnen von ihm behaupteten Zusatzaufträge leistete und was diese kosteten. Dass er dies in genügender Weise getan hätte, ist nicht festgestellt, sondern wird im Gegenteil verneint. Dem Beschwerdeführer gelingt es nicht, Willkür oder eine offensichtlich unrichtige Sachverhaltsfeststellung aufzuzeigen, indem er (seitenweise) ausführt, dass er nach seiner Sicht der Dinge der Substantiierungspflicht nachgekommen sei. Aus den Ausführungen auf den Seiten 15-23 der Klageschrift ist entgegen der Ansicht des Beschwerdeführers gerade nicht "klipp und klar" ersichtlich, dass und welche Zusatzaufträge ihm von der Beschwerdegegnerin erteilt wurden und dass und zu welchem Preis er diese ausführte. Es wird dort - teilweise nur mit Stichworten - über den Verlauf der Arbeiten berichtet und dabei verschiedentlich Mehraufwand behauptet, sodann werden angebliche Zusatzarbeiten aufgelistet etc. Die Erteilung eigentlicher Zusatzaufträge durch die Beschwerdegegnerin, deren Inhalt und Kosten, wird hingegen nicht, jedenfalls nicht hinlänglich bestimmt, dargelegt. Auch in seinem Plädoyer behauptete er lediglich in verschiedener Hinsicht pauschal einen "Mehraufwand" und verwies auf den "Aktenordner" (S. 7 f., act. 96 f.), ohne einen Zusatzauftrag der Beschwerdegegnerin, dessen Inhalt und Preis konkret zu substantiieren. Was die Werkstattplanung anbelangt, zu der sich der Beschwerdeführer auf seine Ausführungen im Plädoyer S. 17 f. (act. 106 f.) beruft, so hat er dort zwar behauptet, diese Arbeiten seien ihm von der Beschwerdegegnerin (und nicht von der Q._ AG) vergeben worden, wobei der verrechnete Preis unter den Werkpreis von Fr. 12'000.-- zu liegen gekommen sei. Nachdem die Beschwerdegegnerin aber ihrerseits stets und spezifisch bestritten hatte, den Beschwerdeführer mit der Werkstattplanung beauftragt zu haben, ist es nicht geradezu willkürlich, wenn diese blosse Behauptung ohne weitere Substantiierung oder Nennung eines Belegs - der Beschwerdeführer legt nicht mit Aktenhinweisen dar, dass er für diese konkrete Behauptung Belege bzw. Beweise angeboten hätte - nicht als hinlänglich substantiierter Tatsachenvortrag erachtet und darüber nicht Beweis erhoben wurde.
Schliesslich betont der Beschwerdeführer, er habe in seinem Plädoyer vom 23. März 2009 seine Aufstellung/Berechnung vom gleichen Tag als Beilage 3 zum integrierenden Bestandteil seines Plädoyers erklärt. Entgegen der Vorinstanz habe er somit nicht einfach auf Beilagen verwiesen, sondern sei mit dieser Aufstellung den Substantiierungsanforderungen vollumfänglich nachgekommen. Indem die Vorinstanz dem Beschwerdeführer dennoch mangelnde Substantiierung vorgeworfen habe, hat sie nach Ansicht des Beschwerdeführers Bundesrecht (<ref-law>) vereitelt bzw. "falsch, aktenwidrig und willkürlich" entschieden. Dieser Rüge kann bereits deshalb nicht gefolgt werden, weil der Beschwerdeführer es unterlässt, mit präzisen Aktenhinweisen aufzuzeigen, dass er sich vor der Vorinstanz auf die genannte Aufstellung und seine daraus abgeleitete Argumentation berufen hätte. Das Bundesgericht sucht nicht selbst in den Akten, sondern verlangt entsprechende präzise Aktenhinweise (vgl. Erwägung 2.2). Solche Hinweise wären umso mehr nötig, als dem angefochtenen Urteil zu der genannten Aufstellung keine Erwägungen zu entnehmen sind. Im Übrigen bliebe der Vorwurf ungenügender Substantiierung trotz dieser Aufstellung jedenfalls insoweit bestehen, als mit der Auflistung des angeblichen Aufwandes bezüglich des Angebotes vom 22. August 2007 und bezüglich angeblicher "Zusatzarbeiten für Werkplanungen" und "Zusatzarbeiten für die Stadt Y._" noch nicht dargetan ist, dass und welche Zusatzaufträge die Beschwerdegegnerin dem Beschwerdeführer erteilt hat.
7. Die Beschwerde ist 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). Der Rechtsvertreter der Beschwerdegegnerin hat eine Kostennote über Fr. 3'912.30 eingereicht. Nachdem das vorliegende Beschwerdeverfahren keine besonderen Schwierigkeiten bot und die Thematik im Wesentlichen auf die Frage hinlänglicher Substantiierung beschränkt war, rechtfertigt es sich, die Parteientschädigung auf Fr. 3'000.-- zu bestimmen (vgl. Art. 3 Reglement über die Parteientschädigung und die Entschädigung an die amtliche Vertretung im Verfahren vor dem Bundesgericht vom 31. März 2006, SR 173.110.210.3).

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. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 19. Juli 2011
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Die Gerichtsschreiberin:
Klett Hotz