Sachverhalt: A. Der Schweizer Hotelier-Verein (SHV), Bern, (Beschwerdeführer), ein Branchenverband der Schweizer Hotellerie, verwendete erstmals im Jahr 1979 Sterne für die Klassifizierung ihm angeschlossener Hotels. Seit etwa November 2004 bietet der Beschwerdeführer seine (entgeltliche) Klassifizierung auch Nichtmitgliedern an. Die diesbezüglichen Garantiemarken des Beschwerdeführers wurden am 3. März 2005 als Nrn. 531 266 - 531 269 sowie Nr. 531 250 im schweizerischen Markenregister eingetragen. Die Wort-/Bildmarken unterscheiden sich nur durch die Anzahl Sterne. Die eingetragene Marke mit drei Sternen sieht zum Beispiel wie folgt aus: GastroSuisse mit Sitz in Zürich (Beschwerdegegner) ist ebenfalls ein als Verein organisierter Branchenverband der Hotellerie und Gastronomie. Er führte mit dem Beschwerdeführer seit etwa dem Jahr 2003 Gespräche darüber, wie die über 60 % der nicht klassifizierten Betriebe, vornehmlich kleinere und mittlere Beherbergungsstätten, klassifiziert werden könnten. Zu einer gemeinsamen Lösung kam es nicht. Am 8. November 2005 hinterlegte der Beschwerdegegner zehn Wort-/Bildmarken mit den Nrn. 541 117 bis 541 126 nach der Art der folgenden Eintragungen: Der Beschwerdegegner beabsichtigte, unter Verwendung dieser Zeichen ein eigenes Klassifikationssystem einzurichten. B. B.a. In der Folge leitete der Beschwerdeführer ein Massnahmeverfahren vor dem Handelsgericht Zürich ein. Mit Verfügung vom 29. Mai 2006 verbot der Einzelrichter am Handelsgericht des Kantons Zürich dem Beschwerdegegner vorsorglich, "im Zusammenhang mit der Bewertung von Beherbergungseinrichtungen Sterne - sei es in Alleinstellung oder in Kombination mit weiteren Elementen - zu verwenden, Dritte mit solchen Sternen auszuzeichnen oder solche Sterne, seien diese selbst oder von Dritten genutzt, zu bewerben oder Dritten den Gebrauch seiner CH-Marken 541 117 bis 541 126 zu gestatten". B.b. Innert der vom Einzelrichter gesetzten Frist klagte der Beschwerdeführer beim Handelsgericht Zürich mit den Rechtsbegehren, es sei dem Beschwerdegegner im Zusammenhang mit der Bewertung von Beherbergungseinrichtungen die Verwendung von Sternen bzw. eventualiter der Zeichen entsprechend den Marken Nrn. 541 117 bis 541 126 zu untersagen und es seien die genannten zehn Marken für nichtig zu erklären. Der Beschwerdegegner erhob Eventualwiderklage. Mit Beschluss vom 6. Februar 2009 trat das Handelsgericht des Kantons Zürich auf die Eventualwiderklage des Beschwerdegegners nicht ein (Dispositiv-Ziffer 1). Die im Massnahmeverfahren mit Verfügung vom 29. Mai 2006 angeordneten vorsorglichen Massnahmen hob es wieder auf und auferlegte die Verfahrenskosten für das Massnahmeverfahren dem Beschwerdeführer (Dispositiv-Ziffern 2-5). Mit Urteil vom gleichen Tag wies das Handelsgericht die Klage des Beschwerdeführers ab. Das Handelsgericht erwog, dass Sterne im Zusammenhang mit der Klassifizierung von Beherbergungseinrichtungen dem Gemeingut angehörten und daher vom Markenschutz ausgeschlossen seien. Es brachte hierzu die folgenden drei selbständigen Eventualbegründungen vor: Erstens dienten Sterne für Beherbergungseinrichtungen als blosse Beschaffenheitsangaben im Sinne der Bezeichnung von Qualitätsstufen. Zweitens könnten Sterne auch als elementare (einfache, primitive) Zeichen gesehen werden, die im Markt vielfältig Verwendung fänden, weshalb ihnen die Unterscheidungskraft abgehe. Schliesslich könne man Sterne auch als Freizeichen betrachten, da sie für die Klassifizierung von Beherbergungseinrichtungen infolge allgemein bekannter Verwendung für den gleichen Zweck durch diverse Marktteilnehmer während Jahrzenten die Kennzeichnungskraft verloren hätten. Eine allenfalls demoskopisch feststellbare Verkehrsdurchsetzung ändere zudem nichts an der Schutzlosigkeit, da vor und nach 1979, als der Beschwerdeführer seinen ersten Hotelführer auf den Markt brachte, Sterne als Klassifizierungsmittel für Hotels und andere Beherbergungseinrichtungen durch diverse Anbieter verwendet worden seien, und zwar immer mit den fünf Kategorien und bis in die jüngste Zeit. Vielmehr sei eine überragende Popularität der Klassifizierung mittels Sternen festzustellen, die historisch und aktuell den Tourismusmarkt im Allgemeinen und den Markt für Beherbergungsmöglichkeiten im Besonderen präge. In Bezug auf die Verwendung von Sternen zur Klassifizierung von Beherbergungseinrichtungen bejahte das Handelsgericht deshalb ein absolutes Freihaltebedürfnis. Entsprechend könne den Sternen in den Klagemarken keine besondere Kennzeichnungskraft zugemessen werden. Den Klagemarken komme daher in ihrer Gesamtwirkung nur ein geringer Schutzbereich zu. Die optischen Unterschiede im Vergleich zu den Zeichen des Beschwerdegegners seien erheblich, wobei nicht zuletzt Namen und Logo des Beschwerdegegners unterscheidend wirkten. Das Handelsgericht verneinte daher eine Verwechslungsgefahr. Auch aus Sicht des Lauterkeitsrechts sei keine Rechtsverletzung auszumachen. 