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. 