Sachverhalt:
A. Die A._ AG ist Eigentümerin des Geschäftshauses X._ an der Strasse X._ in Y._. Sie beauftragte die B._ AG mit der Totalsanierung dieses Hauses. Die Generalunternehmerin zog die C._ AG als Subunternehmerin bei, welche einen Teil der Arbeiten, nämlich die Isolation und die Abdichtungen an der Fassade, der D._ AG übertrug. Diese Arbeiten waren in drei Etappen aufgeteilt. Die erste betraf den mittleren, die zweite den südwestlichen und die dritte den nordöstlichen Gebäudeteil. Die D._ AG begann in der Woche vom 12.-17. Juni 2005 mit den Arbeiten. Im August 2005 unterzeichneten die Subunternehmerin und die D._ AG einen entsprechenden Werkvertrag. Letztere stellte ihre Arbeiten am Gebäude am 20. Februar 2006 ein, nachdem sie vom bevorstehenden Konkurs der Subunternehmerin erfahren hatte, der zwei Tage später eröffnet wurde. Die D._ AG gab im Konkurs der Subunternehmerin eine Werklohnforderung von Fr. 84'997.00 ein.
B. Am 7. April 2006 stellte die D._ AG (Klägerin) beim Audienzrichteramt am Bezirksgericht Zürich ein Gesuch um vorläufige Eintragung eines Bauhandwerkerpfandrechts für eine Forderung von Fr. 84'997.-- nebst Zins zu 5 % seit 7. April 2006 auf der Liegenschaft der A._ AG (Beklagte) an der Strasse X._ in Y._. Das Audienzrichteramt entsprach diesem Gesuch mit Verfügung vom 7. April 2006 und setzte der Klägerin am 25. August 2006 Frist an, um beim zuständigen Gericht eine Klage auf Feststellung der Forderung als Pfandsumme und definitive Eintragung des Pfandrechts gegen die Beklagte anzuheben. Die Klägerin reichte die entsprechende Klage am 12. Oktober 2006 beim Handelsgericht des Kantons Zürich ein.
Mit Verfügung vom 3. November 2006 stellte das Audienzrichteramt fest, dass die Beklagte durch die Hinterlegung von Fr. 107'000.-- hinreichende Sicherheit geleistet hatte und wies das Grundbuchamt Zürich-Altstetten an, das vorläufig eingetragene Bauhandwerkerpfandrecht zu löschen.
Mit Eingabe vom 12. April 2007 änderte die Klägerin ihre Begehren dahingehend, dass sie neben der Feststellung der Pfandsumme verlangte, es sei festzustellen, dass die Klägerin berechtigt sei, die an Stelle des gelöschten Bauhandwerkerpfandrechts getretene Barsicherheit in Anspruch zu nehmen.
Die Instruktionsrichterin erliess am 12. Juni 2007 eine Verfügung mit folgenden Substantiierungshinweisen:
"Die Klägerin wird insbesondere aufgefordert, in der Rechtsschrift im Einzelnen darzulegen,
- wann wer welche Arbeiten ausgeführt hat;
- die einzelnen Positionen der geltend gemachten Pfandsumme.
Sodann sind hinsichtlich der Nachtrags- und Regiearbeiten die behaupteten Vereinbarungen insbesondere in zeitlicher Hinsicht zu substanziieren sowie, soweit noch nicht erfolgt, darzutun, welche Personen wann welche konkreten Vereinbarungen getroffen haben."
Mit Urteil vom 18. Februar 2009 wies das Handelsgericht die Klage wegen ungenügender Substantiierung ab.
C. Die Klägerin erhob Beschwerde in Zivilsachen mit den Begehren, das Urteil des Handelsgerichts vom 18. Februar 2009 sei aufzuheben und die Sache sei zur Feststellung des Sachverhalts und Neubeurteilung im Sinne der Erwägungen an das Handelsgericht zurückzuweisen. Eventuell sei die Klage gutzuheissen.
Zudem stellte die Beschwerdeführerin ein Gesuch um aufschiebende Wirkung, das mit Präsidialverfügung vom 7. Mai 2009 gutgeheissen wurde. In einer Beschwerdeergänzung vom 27. März 2009 ersuchte die Beschwerdeführerin um Zulassung eines Novums.
Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde. Das Handelsgericht verzichtet auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Gegenstand des Verfahrens bildet eine Zivilsache (<ref-law>). Die Rechtsbegehren der Beschwerdeführerin sind im kantonalen Verfahren nicht geschützt worden (<ref-law>), der massgebende Streitwert beträgt mehr als Fr. 30'000.-- (Art. 51 i.V.m. <ref-law>), und die Beschwerdefrist ist auch bezüglich der Beschwerdeergänzung eingehalten (<ref-law>).
1.2 Weiter setzt die Beschwerde in Zivilsachen voraus, dass das angefochtene Urteil letztinstanzlich ist (<ref-law>). Gegen das Urteil des Handelsgerichts hätte die kantonale Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich nach <ref-law>/ZH erhoben werden können, was die Beschwerdeführerin unterliess. Das Urteil ist daher insoweit nicht kantonal letztinstanzlich, als es vom Kassationsgericht hätte überprüft werden können. Ausgeschlossen ist die Nichtigkeitsbeschwerde, wenn das Bundesgericht einen Mangel frei überprüfen kann, wobei sie stets zulässig ist, wenn eine Verletzung von Art. 8, 9, 29 oder 30 BV oder von Art. 6 EMRK geltend gemacht wird (<ref-law>/ZH; vgl. dazu <ref-ruling> E. 3.2 S. 586 f. mit Hinweisen). Die Letztinstanzlichkeit des angefochtenen Urteils ist daher bezüglich der Rüge der willkürlichen Anwendung kantonalen Rechts (<ref-law>) zu verneinen, weshalb auf solche Rügen nicht eingetreten werden kann. Bezüglich der Rüge der Verletzung von Bundeszivilrecht ist das Urteil des Handelsgerichts dagegen ein letztinstanzlicher Entscheid (vgl. Urteil 4A_398/2008 vom 18. Dezember 2008, E. 1.2.2).
1.3 Gemäss <ref-law> können neue Tatsachen und Beweismittel nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt. Dies ist grundsätzlich bei Tatsachen zu verneinen, welche erst nach der Fällung des angefochtenen Entscheids eingetreten sind, da das Bundesgericht die Rechtsanwendung gestützt auf den Sachverhalt in diesem Zeitpunkt zu überprüfen hat (BERNARD CORBOZ, in: Corboz und andere, Commentaire de la LTF, 2009, N. 26 zu <ref-law>; URLICH MEYER, in: Basler Kommentar, Bundesgerichtsgesetz, 2008, N. 43 zu <ref-law>). Die Angabe der Beschwerdeführerin, nach der Fällung des angefochtenen Entscheids am 18. Februar 2009 habe die Konkursverwaltung der C._ AG am 4. März 2009 die in ihrem Konkurs eingegebene Werklohnforderung von Fr. 84'997.-- in den Kollokationsplan aufgenommen, ist daher als unzulässige neue Tatsachenbehauptung nicht zu hören.
2. 2.1 Wie weit die anspruchsbegründenden Tatsachen inhaltlich zu substantiieren sind, damit sie unter die massgeblichen Bestimmungen des materiellen Rechts subsumiert werden können, bestimmt das materielle Bundesrecht. Die jeweiligen Anforderungen ergeben sich einerseits aus den Tatbestandsmerkmalen der angerufenen Norm und anderseits aus dem prozessualen Verhalten der Gegenpartei. Tatsachenbehauptungen müssen dabei so konkret formuliert sein, dass ein substantiiertes Bestreiten möglich ist oder der Gegenbeweis angetreten werden kann. 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 (<ref-ruling> E. 2b mit Hinweisen). Auf welchem Weg ein subsumptionsfähiger Sachverhalt erlangt werden soll, bestimmt dagegen das kantonale Prozessrecht. Ihm bleibt die Regelung der Frage vorbehalten, in welcher Form und bis zu welchem Zeitpunkt die inhaltlich genügenden Sachvorbringen in das Verfahren einzuführen sind. Kantonales Prozessrecht entscheidet auch darüber, ob eine Ergänzung der Sachvorbringen aufgrund des Beweisverfahrens zulässig ist oder ob bereits die vorgängigen Behauptungen so konkret und detailliert sein müssen, dass das Beweisverfahren allein noch ihrer Überprüfung dient (<ref-ruling> E. 2c; <ref-ruling> E. 3; Urteil 4C.351/2000 vom 20. Juli 2001 E. 3c).
2.2 Der Anspruch auf Errichtung eines gesetzlichen Grundpfandrechts besteht für die Forderungen der Handwerker oder Unternehmer, die zu Bauten oder andern Werken auf einem Grundstücke Material und Arbeit oder Arbeit allein geliefert haben, an diesem Grundstücke, sei es, dass sie den Grundeigentümer oder einen Unternehmer zum Schuldner haben (<ref-law>). Die Eintragung des Pfandrechts der Handwerker und Unternehmer hat bis spätestens drei Monate nach der Vollendung ihrer Arbeit zu geschehen (<ref-law>).
2.3 Das Handelsgericht kam zum Ergebnis, die Beschwerdeführerin habe die von ihr geltend gemachten Arbeiten als Handwerkerin oder Unternehmerin im Sinne von <ref-law> erbracht und die dreimonatige Frist zur Eintragung des Bauhandwerkerpfandrechts gewahrt. Jedoch habe die Beschwerdeführerin die pfandberechtigten Arbeiten nicht genügend substantiiert. Die Beschwerdeführerin habe in der Klageschrift bezüglich der in der ersten und zweiten Etappe geleisteten Arbeiten auf den Werkvertrag, die vorangegangenen Preisanfragen und die dazugehörigen Schnittpläne und Massenauszüge verwiesen. Nach der Bestreitung durch die Beschwerdegegnerin in der Klageantwort hätte die Beschwerdeführerin ihr an sich schlüssiges Vorbringen nicht nur in den Grundzügen, sondern so umfassend und klar darzulegen gehabt, dass darüber Beweis abgenommen werden konnte, zumal sie vom Gericht mit Verfügung vom 12. Juni 2007 aufgefordert worden sei, anzugeben, wann wer welche Arbeiten ausgeführt hat. Dies habe die Beschwerdeführerin nicht getan. Hierzu wäre sie aber aufgrund der Bestreitungen der Beschwerdegegnerin verpflichtet gewesen. Zwar habe diese an der Referentenaudienz vom 31. Mai 2007 ausgeführt, ihres Wissens habe die Beschwerdeführerin 98 % der ersten Etappe und ca. 70 % der zweiten Etappe erfüllt. Diese Aussage habe die Beschwerdegegnerin jedoch zurückgezogen, indem sie in der Duplik an ihrer Bestreitung [in der Klageantwort] festgehalten habe. Bezüglich der ersten Etappe habe die Beschwerdeführerin angeführt, dass 100 % verrechnet worden seien, obwohl sie im Prozess geltend gemacht habe, es seien 98 % geleistet worden. Welche Arbeiten die Differenz ausmachten, erhelle weder aus den Ausführungen der Beschwerdeführerin noch aus den Beilagen, auf die sie verweise. Insgesamt gehe aus den Ausführungen der Beschwerdeführerin nicht hervor, wer wann welche Arbeiten ausgeführt habe und worin die 98 % der geleisteten Arbeit bestanden hätten. Bezüglich der zweiten Etappe liefere die Beschwerdeführerin in der Replik eine Aufstellung, was gemäss Vertrag hätte geleistet werden sollen und was effektiv erbracht worden sei. Wer diese Arbeiten wann erbracht habe, führe die Beschwerdeführerin wiederum nicht aus.
2.4 Die Beschwerdeführerin macht geltend, im vorliegenden Werkvertrag sei gemäss <ref-law> ein Pauschal- bzw. Festpreis vereinbart worden, bei dem der Anspruch auf den Werklohn einzig von der Erstellung des Werkes abhänge. Nicht relevant sei deshalb, welche Person wann welche Arbeit erbracht habe. Indem das Obergericht entsprechende Angaben verlangte, habe es zu hohe Anforderungen an die Substantiierungspflicht gestellt und damit Bundesrecht verletzt. Die Beschwerdeführerin habe behauptet, 100 % der Leistungen der ersten Etappe erbracht zu haben. Die vom Handelsgericht genannte Zahl von 98 % entspreche einer Behauptung der Beschwerdegegnerin. Bezüglich der zweiten Etappe habe die Beschwerdeführerin die einzelnen tatsächlich erbrachten Leistungen dem "Soll nach Vertrag" gegenübergestellt. Auf dieser Basis könnten Beweise abgenommen werden.
2.5 Das Bauhandwerkerpfandrecht findet seine Rechtfertigung darin, dass Bauarbeiten grundsätzlich geeignet sind, den Wert der Baute zu vermehren. Nach dem Wortlaut des Gesetzes besteht die Pfandsumme jedoch für Forderungen der Handwerker oder Unternehmer und wird daher nach dem Vertragsverhältnis mit dem Besteller bestimmt und nicht durch den objektiven Mehrwert, den die Bauarbeiten allenfalls geschaffen haben (<ref-ruling> E. 4d S. 474). Demnach ist bei der Bestimmung der Pfandsumme darauf abzustellen, ob der massgebende Werkvertrag einen zum voraus genau bestimmten Preis im Sinne von <ref-law> in Form eines resultatbezogenen Pauschal-, Global oder Einheitspreises oder eine Vergütung unter Berücksichtigung des erforderlichen Zeitaufwands (Regiearbeiten) vorsieht (Urteil 4C.385/2005 vom 31. Januar 2006 E. 5). Die bei einem Vertragsrücktritt geschuldete Vergütung für die bereits geleistete Arbeit richtet sich ebenfalls proportional nach dem vertraglich vereinbarten Preis, wobei gegebenenfalls durch Expertise festgestellt werden muss, in welchem Ausmass das Werk erstellt wurde (PETER GAUCH, Der Werkvertrag, 4. Aufl. 1996, S. 207 Rz. 730; BERNARD CORBOZ, Werkvertrag V, Das Erlöschen des Vertrages, in: SJK Nr. 462, S. 10; vgl. auch BGE 25 II 396 E. 2 S. 400 f.).
2.6 Gemäss dem im August 2005 unterzeichneten, von der Vorinstanz angeführten Werkvertrag vereinbarten die Parteien einen Pauschalpreis von Fr. 180'000.--, der auf den Massangaben und Preisen der Beilage 5 zum Werkvertrag basiert. In dieser Beilage werden für jede Etappe die zu erbringenden Werkleistungen nach Kategorien mengenmässig umschrieben und der dafür pro Meter bzw. Quadratmeter geschuldete Preis bestimmt (vgl. Beilage 5a). Damit haben die Parteien insoweit einen festen Preis gemäss <ref-law> vereinbart, der sich allein nach dem erstellten Werk und nicht nach der zur Erstellung erforderlichen Arbeit richtet (vgl. <ref-law>). Welcher Handwerker welche Arbeit zu erbringen hat, wurde nicht vereinbart. Demnach ist nicht erheblich, welcher der Angestellten der Beschwerdeführerin die Arbeiten geleistet hatte. Da die Beschwerdegegnerin nicht einwendete, gewisse Arbeiten seien zu früh oder zu spät erfolgt, ist der Zeitpunkt der Leistung ebenfalls nicht relevant. Somit hat das Handelsgericht bundesrechtswidrige Anforderungen an die Substantiierung gestellt, wenn es von der Beschwerdeführerin Angaben dazu verlangte, wann wer welche Arbeiten ausführte. Zur Substantiierung der Leistungen genügte die Angabe, welche Leistungen in welchem Umfang erbracht wurden. Dieser Obliegenheit ist die Beschwerdeführerin nachgekommen, indem sie sowohl in der Klage (S. 19 Rz. 51) als auch in der Replik (S. 7) vorbrachte, sie habe alle Arbeiten der ersten Etappe ausgeführt und den Umfang der tatsächlich erbrachten Teilleistung der zweiten Etappe in der Replik (S. 7 Rz. 13) auflistete. Die Annahme des Handelsgerichts, die Beschwerdeführerin habe angegeben, 98 % der Leistungen der 1. Etappe erbracht zu haben, ist offensichtlich unrichtig, da diese Angabe von der Beschwerdegegnerin stammt. Der Sachverhalt ist daher insoweit gemäss <ref-law> zu berichtigen.
3. 3.1 Das Handelsgericht erachtete die Forderungen, welche die Beschwerdeführerin aus vier Nachtragsofferten ableitete, bezüglich der erbrachten Leistungen als ungenügend substantiiert, da sich in den Rechtsschriften bezüglich der ersten, zweiten und vierten Nachtragsofferte keine Angaben dazu fänden, was die Beschwerdeführerin tatsächlich geleistet habe und es nicht Aufgabe des Gerichts sein könne, die Behauptungen der Beschwerdeführerin in den Beilagen zu suchen. In der dritten Nachtragsofferte vom 10. August 2005 sei zwar von insgesamt 992 m2 die Rede, wogegen gemäss Act. 3.7.3 Pos. 4 lediglich 307 m2 fakturiert worden seien, weshalb unklar bleibe, worin die Leistung der Beschwerdeführerin bestanden habe.
3.2 Die Beschwerdeführerin wendet ein, das Bestehen einer Schuld könne auch durch Anerkennung nachgewiesen werden. Die Beschwerdeführerin habe in der Replik geltend gemacht, die C._ AG habe die Rechnungen zu den Nachtragsofferten "zur Zahlung freigegeben" und damit anerkannt. Indem das Handelsgericht die Behauptung der Anerkennung der Forderungen aus Nachtragsofferten durch die Schuldnerin nicht genügen liess und stattdessen detaillierte Angaben zu den geleisteten Arbeiten verlangte, habe es Anforderungen an die Substantiierung gestellt, welche nicht aus den Tatbestandsmerkmalen des <ref-law> abgeleitet werden könnten.
3.3 Die Eintragung des Bauhandwerkerpfandrechts darf nur erfolgen, wenn die Forderung vom Eigentümer anerkannt oder gerichtlich festgestellt ist (<ref-law>). Fraglich ist, ob eine Anerkennung einer Forderung durch einen General- oder Subunternehmer der Anerkennung durch den Eigentümer gleichgestellt werden kann. Die Frage kann jedoch offen bleiben. Auch die Behauptung einer Forderungsanerkennung setzt voraus, dass im Gerichtsverfahren formgerecht geltend gemacht wird, in welcher Höhe die Forderung anerkannt wurde. Da die Beschwerdeführerin die Höhe der behaupteten Forderungsanerkennung in den Rechtsschriften nicht nannte, hätte sie darin insoweit die erbrachte Leistung und den dafür vereinbarten Preis nennen müssen, zumal die Erwägung des Handelsgerichts, dass es die Behauptungen der Parteien nicht in den Beilagen zu suchen habe, auf kantonalem Prozessrecht beruht und mangels Ausschöpfung des Instanzenzuges nicht überprüft werden kann (vgl. E. 1.2). Dass aber der Leistungsumfang betreffend die erste, zweite und vierte Nachtragsofferte nicht in den Rechtsschriften genannt wird, bestreitet die Beschwerdeführerin nicht. Sie macht jedoch geltend, sie habe in der Klage (Rz. 35) bezüglich der dritten Nachtragsofferte behauptet, einen Mehrpreis von Fr. 7.50 pro m2 mit den insgesamt 922 m2 in der Position 12 des Massenauszuges multipliziert zu haben. Damit habe sie konkretisiert, dass sie von einer Leistung von 922 m2 ausgehe, selbst wenn diese Behauptung in einem Widerspruch zu einer anderen Behauptung in den Rechtsschriften stehen würde.
3.4 Die Beschwerdeführerin hat in der Klage auf Seite 14 Rz. 35 vorgebracht:
"Die Klägerin offerierte am 10. August [2005] einen Mehrpreis von CHF 7.50 pro m2, was sie mit den insgesamt 922 m2 in der Position 12 des Massenauszuges multiplizierte. Auch damit war die Firma C._ einverstanden, was mit der Zustimmung zur Rechnung Nr. 17706 (ES act. 3/7.3, dat. 8.12.2005, dort Pos. 04, S. 2/4) durch R._ von der Firma C._ nochmals bestätigt wurde".
Die in der Klage genannten 922 m2 betreffen damit lediglich die Offertstellung. Welche Leistung tatsächlich erbracht worden sein soll, geht aus der Klage nicht hervor. Der Leistungsumfang könnte höchstens aus der angerufenen Rechnung abgeleitet werden, welche in der 4. Position jedoch lediglich 307 m2 aufführt. Insoweit hat das Handelsgericht mit der Annahme, die Beschwerdeführerin habe in ihren Rechtsschriften die tatsächlich gestützt auf die Nachtragsofferte vom 10. August 2005 erbrachte Leistung, mithin auch eine mögliche Anerkennung, nicht genügend substantiiert, kein Bundesrecht verletzt.
4. 4.1 Zu den Regiearbeiten vom 11. Oktober 2005 erwog das Handelsgericht, die Angaben der Beschwerdeführerin seien genügend substantiiert. Dennoch erübrige sich eine Beweisabnahme, weil die Beschwerdeführerin die Pfandsumme nicht hinreichend dargelegt habe. Auch die Regiearbeiten vom 20. Dezember 2005 seien betreffend Arbeit und Anzahl Arbeitsstunden rechtsgenügend substantiiert. Es fehlten jedoch Angaben dazu, wer von der Beschwerdeführerin an der diesen Regiearbeiten zugrunde liegenden Vereinbarung beteiligt gewesen sei, weshalb ein konkreter Beweissatz auch hier nicht möglich sei.
4.2 Die Beschwerdeführerin wendet ein, es sei nicht ersichtlich, wie sich aus <ref-law> ergeben soll, dass Klarheit darüber bestehen müsse, welche natürliche Person eine juristische Person beim Abschluss eines Vertrages vertreten hat.
4.3 Die Frage, wer für eine juristische Person handelt, ist erheblich, wenn etwa eingewendet wird, die betreffende Person sei nicht vertretungsberechtigt gewesen. Eine ohne Vertretungsmacht getroffene Vereinbarung kann jedoch vom Vertretenen genehmigt werden (<ref-law>). Da die Beschwerdeführerin mit der vorliegenden Klage eindeutig zum Ausdruck brachte, dass sie die Vereinbarung betreffend die Regiearbeiten vom 20. Dezember 2005 gelten lassen wollte, ist nicht erheblich, wer auf ihrer Seite an dieser Vereinbarung beteiligt war. Somit genügt die Behauptung, dass die Beschwerdegegnerin mit einer entsprechenden Offerte der Beschwerdeführerin einverstanden war. Das Handelsgericht hat demnach Bundesrecht verletzt, wenn es in diesem Zusammenhang Angaben zur Person verlangte, welche die Beschwerdeführerin vertrat.
5. 5.1 Schliesslich nahm das Handelsgericht an, die Beschwerdeführerin habe die Höhe der Pfandforderung nicht formgerecht substantiiert. Trotz Substantiierungshinweis habe sich die Beschwerdeführerin in der Replik damit begnügt, ihre Beilage vom 22. Februar 2006 als integrierenden Bestandteil ihrer Eingabe zu erklären, ohne die einzelnen Positionen zu erläutern.
5.2 Die Beschwerdeführerin wendet ein, soweit die Zusammenstellung vom 22. Februar 2006 nach kantonalem Recht nicht als Behauptung zugelassen werde, ergäben sich die geforderten Beträge aus den Rechtsschriften. Dies müsse genügen, da der Anspruch auf Zulassung zum Beweis nach <ref-law> nicht davon abhängig gemacht werden dürfe, dass ein Kläger die einzelnen Positionen seines Anspruchs in einer Liste zusammenstelle und addiere.
5.3 Wie bereits dargelegt, hat die Beschwerdeführerin bezüglich der ersten und zweiten Etappe und den Regiearbeiten die erbrachten Leistungen hinreichend substantiiert (vgl. E 2.6 und E. 4 hiervor). Die entsprechenden Forderungsbeträge für die erste und zweite Etappe hat die Beschwerdeführerin in der Replik (S. 6 ff. Rz. 12 ff.), aufgeteilt nach den verschiedenen werkvertraglich bestimmten Leistungen und dem Leistungsumfang, aufgelistet und auf diese Weise Summen von Fr. 60'367.60 und Fr. 66'831.20 abzüglich 15 % Rabatt plus 7.6 % MWST errechnet, was einem Gesamtbetrag von Fr. 116'336.02 entspricht. Zudem verlangte die Beschwerdeführerin in der Klage (S. 15 f. Rz. 37 f.) für am 11. Oktober und 20. Dezember 2005 erbrachte Regiearbeiten von drei und fünf Arbeitsstunden ausdrücklich Fr. 285.70 bzw. Fr. 545.45. Aus den Rechtsschriften ergeben sich somit geltend gemachte Pfandforderungen von Fr. 116'336.02, Fr. 285.70 und Fr. 545.45, was abzüglich der Akontozahlungen von Fr. 58'104.-- einen Betrag von Fr. 59'063.17 ergibt. In diesem Umfang hat die Beschwerdeführerin nicht nur die erbrachten Leistungen, sondern auch die entsprechenden Pfandforderungen genügend substantiiert behauptet. Das Handelsgericht hat daher Bundesrecht verletzt, wenn es insoweit eine genügende Substantiierung der Klage verneinte.
6. Nach dem Gesagten ist die Beschwerde teilweise gutzuheissen, das angefochtene Urteil aufzuheben und die Sache - soweit taugliche Beweismittel prozessual gehörig angeboten wurden (<ref-ruling> E. 2.6; <ref-ruling> E. 3c S. 223 ff.) - zur Durchführung eines Beweisverfahrens und zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Da die Beschwerdeführerin bezüglich der Substantiierung nur etwa zu drei Vierteln der Forderungssumme obsiegt, rechtfertigt es sich, die Gerichtskosten den Parteien in diesem Verhältnis aufzuerlegen und die Beschwerdegegnerin zu verpflichten, der Beschwerdeführerin eine reduzierte Parteientschädigung zu entrichten (Art. 66 Abs. 1 und Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, das Urteil des Handelsgerichts des Kantons Zürich vom 18. Februar 2009 aufgehoben und die Sache zur Durchführung eines Beweisverfahrens und zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Die Gerichtskosten von Fr. 4'000.-- werden der Beschwerdegegnerin zu drei Vierteln und der Beschwerdeführerin zu einem Viertel auferlegt.
3. Die Beschwerdegegnerin hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 2'500.- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 29. Juni 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Gelzer