Sachverhalt:
A. Mit Eingabe vom 11. Dezember 2007 klagte A._ (Beschwerdeführer) beim Handelsgericht des Kantons Zürich gegen die X.Y._ GmbH (Beschwerdegegnerin) sinngemäss auf Feststellung seines Besitzes an der Internet-Domain "x._.ch". Der Experte des WIPO Arbitration and Mediation Centre hatte mit Entscheid vom 16. November 2007 angeordnet, dass der Domain-Name "x._.ch" auf die Beschwerdegegnerin zu übertragen sei.
Das Handelsgericht wies mit Beschluss vom 20. März 2008 ein Begehren des Beschwerdeführers um Gewährung der unentgeltlichen Prozessführung ab und setzte ihm eine Frist bis 16. April 2008 an, um eine Prozesskaution von Fr. 10'600.-- zu leisten, mit der Androhung, dass bei Säumnis auf die Klage nicht eingetreten werde. Dieser Beschluss blieb unangefochten. Der Beschwerdeführer leistete die ihm auferlegte Prozesskaution nicht. Mit Beschluss vom 5. Mai 2008 trat das Handelsgericht androhungsgemäss auf die Klage nicht ein.
B. Mit Urteil vom 10. November 2008 wies das Kassationsgericht die vom Beschwerdeführer gegen den Entscheid des Handelsgerichts vom 5. Mai 2008 erhobene Beschwerde ab.
C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei der Beschluss des Handelsgerichts des Kantons Zürich vom 5. Mai 2008 aufzuheben und es sei dieses anzuweisen, die Sache neu zu beurteilen. Eventualiter sei der Beschluss des Kassationsgerichts des Kantons Zürich vom 10. November 2008 aufzuheben und es sei dieses anzuweisen, die Sache zur Neubeurteilung an das Handelsgericht des Kantons Zürich zurückzuweisen.
Die Beschwerdegegnerin schliesst in ihrer Antwort auf Abweisung der Beschwerde. Sowohl das Kassationsgericht als auch das Handelsgericht des Kantons Zürich haben auf eine Vernehmlassung verzichtet.
D. Mit Präsidialverfügung vom 9. März 2009 wurde der Beschwerde aufschiebende Wirkung gewährt.

Erwägungen:
1. 1.1 Damit ein kantonaler Entscheid mit Beschwerde in Zivilsachen angefochten werden kann, muss der Instanzenzug im Kanton erschöpft sein (<ref-law>). Für Rügen, die mit der Beschwerde in Zivilsachen erhoben werden können, darf kein kantonales Rechtsmittel mehr offen stehen (<ref-ruling> E. 1.3 S. 527). Auf Rügen, die mit kantonaler Nichtigkeitsbeschwerde einer weiteren kantonalen Instanz hätten vorgetragen werden können, ist mangels Letztinstanzlichkeit nicht einzutreten.
Der Beschwerdeführer hat sowohl den Beschluss des Handelsgerichts vom 5. Mai 2008 als auch den Beschluss des Kassationsgerichts vom 10. November 2008 beim Bundesgericht angefochten. Dies ist grundsätzlich zulässig und die Beschwerdefrist ist auch bezüglich des handelsgerichtlichen Entscheids gewahrt (<ref-law>). Soweit sich die Beschwerde gegen den Entscheid des Handelsgerichts vom 5. Mai 2008 richtet, beschränken sich die vorgebrachten Rügen auf die Verletzung des Fairnessgebots (<ref-law> bzw. Art. 6 Ziff. 1 EMRK) sowie des Anspruchs auf unentgeltliche Rechtspflege (<ref-law>) und auf Wahrung von Treu und Glauben (<ref-law>), mithin auf die Verletzung verfassungsmässiger Rechte. Für diese vom Beschwerdeführer mit Beschwerde in Zivilsachen erhobenen Rügen stand nach <ref-law>/ZH die Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich offen (vgl. Frank/Sträuli/Messmer, Kommentar zur zürcherischen Zivilprozessordnung, 3. Aufl. 1997, N. 16 ff. zu <ref-law>/ZH). Eine solche wurde vom Beschwerdeführer auch erhoben. Da der Beschwerdeführer vor Bundesgericht keine Rügegründe geltend macht, die dem Kassationsgericht nicht hätten vorgetragen werden können, fehlt es dem angefochtenen Entscheid des Handelsgerichts insoweit an der Letztinstanzlichkeit (<ref-law>). Auf die dagegen gerichtete Beschwerde kann nicht eingetreten werden.
1.2 Der Beschwerdeführer hatte gegen den Beschluss vom 20. März 2008, mit dem das Handelsgericht sein Begehren um Gewährung der unentgeltlichen Prozessführung abwies, kein Rechtsmittel ergriffen, sondern erst den Endentscheid vom 5. Mai 2008 angefochten. Dennoch richtet sich die Begründung der Beschwerde gegen die Verweigerung der unentgeltlichen Rechtspflege. Dies ist zulässig, da es sich beim Beschluss vom 20. März 2008 um einen Zwischenentscheid im Sinne von <ref-law> handelt und die Unterlassung der selbständigen Anfechtung eines solchen die Anfechtung eines darauf beruhenden Endentscheids nicht ausschliesst (<ref-law>).
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>). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss substantiiert darlegen, inwiefern die Voraussetzungen einer Ausnahme gemäss <ref-law> gegeben sind und das Verfahren bei rechtskonformer Ermittlung des Sachverhalts anders ausgegangen wäre; andernfalls kann ein Sachverhalt, der vom im angefochtenen Entscheid festgestellten abweicht, nicht berücksichtigt werden. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (vgl. <ref-ruling> E. 1.3, 393 E. 7.1, 462 E. 2.4). Im vorliegenden Verfahren ist zudem zu beachten, dass behauptete Rechtsverletzungen, die zunächst mit kantonaler Nichtigkeitsbeschwerde hätten vorgetragen werden können, jedoch nicht gerügt worden sind, mangels Erschöpfung des kantonalen Instanzenzugs (<ref-law>) von vornherein ausser Betracht bleiben müssen.
2.2 Diese Grundsätze verkennt der Beschwerdeführer. Er stellt seinen rechtlichen Ausführungen eine eigene Sachverhaltsdarstellung voran, in der er den Ablauf der Ereignisse sowie des Verfahrens aus seiner Sicht darlegt. Er weicht darin - wie auch in seiner weiteren Beschwerdebegründung - in zahlreichen Punkten von den tatsächlichen Feststellungen der Vorinstanz ab oder erweitert diese, ohne substantiiert Ausnahmen von der Sachverhaltsbindung gemäss Art. 105 Abs. 2 und <ref-law> geltend zu machen. Seine Vorbringen haben insoweit unbeachtet zu bleiben.
3. Soweit sich die Beschwerde gegen den Beschluss des Kassationsgerichts vom 10. November 2008 richtet, rügt der Beschwerdeführer eine Verletzung des Anspruchs auf unentgeltliche Rechtspflege (<ref-law>).
3.1 Nach <ref-law> hat jede Person, die nicht über die erforderlichen Mittel verfügt und deren Rechtsbegehren nicht aussichtslos erscheint, Anspruch auf unentgeltliche Rechtspflege. Falls es zur Wahrung ihrer Rechte notwendig ist, hat sie ausserdem Anspruch auf unentgeltlichen Rechtsbeistand. Als aussichtslos sind nach der bundesgerichtlichen Rechtsprechung Prozessbegehren anzusehen, bei denen aufgrund einer summarischen Prüfung nach den Verhältnissen zur Zeit, zu der das Gesuch um unentgeltliche Rechtspflege gestellt wird, die Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können. Dagegen gilt ein Begehren nicht als aussichtslos, wenn sich Gewinnaussichten und Verlustgefahren ungefähr die Waage halten oder jene nur wenig geringer sind als diese. Massgebend ist, ob eine Partei, die über die nötigen finanziellen Mittel verfügt, sich bei vernünftiger Überlegung zu einem Prozess entschliessen würde; eine Partei soll einen Prozess, den sie auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er sie nichts kostet. Die Rüge einer bedürftigen Partei, ihr verfassungsmässiger Anspruch auf unentgeltliche Rechtspflege sei verletzt, prüft das Bundesgericht in rechtlicher Hinsicht frei. Soweit es um tatsächliche Feststellungen der kantonalen Instanz geht, ist seine Prüfungsbefugnis auf Willkür beschränkt (<ref-law>; <ref-ruling> E. 2.3; <ref-ruling> E. 2.1; je mit Hinweisen).
3.2 Das Kassationsgericht hat im angefochtenen Entscheid erwogen, das Handelsgericht habe das Klagebegehren des Beschwerdeführers als Feststellung der Nichtverletzung einer Marke verstanden und dafür gehalten, die vom Beschwerdeführer in der vorliegend rudimentären Form präsentierten Argumente, zusammen mit dem unklar und ungenügend formulierten Rechtsbegehren und unter Berücksichtigung der vorhandenen Unterlagen ergäben im gegenwärtigen Zeitpunkt Gewinnaussichten, welche erheblich geringer als die Verlustgefahren seien. Das Kassationsgericht kam zum Schluss, die Vorbringen des Beschwerdeführers vermöchten an dieser Einschätzung der Erfolgsaussichten der Klage nichts zu ändern.
Der Beschwerdeführer rügt, das Kassationsgericht habe seine Vorbringen gegen den Beschluss des Handelsgerichts vom 20. März 2008 in Verletzung von <ref-law> verworfen. Er habe sich dagegen gewandt, dass seine Klage als aussichtslos qualifiziert und aus diesem Grund sein Gesuch um Gewährung der unentgeltlichen Rechtspflege abgewiesen worden sei. Das Kassationsgericht hätte die Aussicht seiner Klage mit freier Kognition prüfen und sich nicht auf eine Willkürkognition beschränken dürfen. Das Gericht hätte insbesondere aus den von ihm eingereichten Beilagen, die schon dem Handelsgericht vorgelegen hätten, ersehen können, dass ihm die Priorität am Domain-Namen "www.x._.ch" zustehe, dessen Registrierung älter sei als die Hinterlegung der internationalen Wortmarke "X._" der Beschwerdegegnerin. Seine Domain sei zudem über Jahre hinweg von der Beschwerdegegnerin unangefochten geblieben (Verwirkungseinrede), weshalb das Kassationsgericht nicht hätte zum Schluss kommen dürfen, seine Klage auf Feststellung der Nichtverletzung der Marke sei aussichtslos.
3.3 Der Beschwerdeführer bringt zutreffend vor, dass bei der Beurteilung eines Gesuchs um Gewährung der unentgeltlichen Rechtspflege die Aussichten einer Klage in rechtlicher Hinsicht frei zu prüfen sind. Nachdem das Handelsgericht - wie aus den Feststellungen des angefochtenen Entscheides hervorgeht - die Aussichten der vom Beschwerdeführer eingereichten Klage zutreffend "unter Berücksichtigung der vorhandenen Unterlagen" beurteilt hat, hätte es die Daten der Registrierung der Domain des Beschwerdeführers einerseits und der internationalen Marke der Beschwerdegegnerin anderseits beachten müssen (vgl. etwa <ref-ruling> E. 3c S. 93 f.), was das Kassationsgericht im angefochtenen Entscheid verkennt. Auch wenn über Kollisionen zwischen Domain-Namen und Markenrechten nicht schematisch, sondern durch Abwägung der gegenseitigen Interessen zu entscheiden ist (<ref-ruling> E. 4.3.2; <ref-ruling> E. 3c S. 93; je mit Verweisen), kann unter Berücksichtigung der zeitlichen Priorität der Registrierung der Domain des Beschwerdeführers nicht von Vorneherein angenommen werden, die Gefahr des Unterliegens des Beschwerdeführers im Prozess sei derart hoch, dass die Chance des Obsiegens kaum mehr als ernsthaft bezeichnet werden könne.
Zwar ist das Verhalten des Beschwerdeführers schwer nachvollziehbar, hat er sich doch am Verfahren kaum beteiligt, obwohl er beim Handelsgericht Klage eingereicht hatte. Anderseits ist gerade der Zweck der unentgeltlichen Rechtspflege, den Rechtssuchenden den Zugang zum Gericht zu gewährleisten, weshalb ihnen falls erforderlich auch ein Rechtsbeistand beizugeben ist. Es geht jedenfalls nicht an, eine Klage unter Hinweis auf ein "unklar und ungenügend formuliertes" Rechtsbegehren als aussichtlos zu qualifizieren, obwohl das Klagebegehren zutreffend als ein solches auf Feststellung der Nichtverletzung einer Marke erkannt wurde. Die Vorinstanz hat <ref-law> verletzt, indem sie den Nichteintretensentscheid des Handelsgerichts geschützt hat, das die Klage zu Unrecht als aussichtslos qualifizierte. Das Kassationsgericht hätte diesen Entscheid vielmehr aufheben müssen, so dass das Handelsgericht nach Beurteilung der Bedürftigkeit des Beschwerdeführers über dessen Gesuch um Gewährung der unentgeltlichen Rechtspflege neu entscheidet.
4. Nach dem Gesagten ist auf die Beschwerde nicht einzutreten, soweit sie sich gegen den Beschluss des Handelsgerichts vom 5. Mai 2008 richtet. Im Übrigen ist die Beschwerde gutzuheissen, der Beschluss des Kassationsgerichts vom 10. November 2008 ist aufzuheben und die Sache an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin unterliegt im Beschwerdeverfahren, weshalb ihr grundsätzlich die Gerichtskosten zu auferlegen wären (<ref-law>). Allerdings ist ihre Beteiligung am vorliegenden Verfahren darauf zurückzuführen, dass der Beschwerdeführer erst den Nichteintretensentscheid vom 5. Mai 2008 nach Ausbleiben des auferlegten Prozesskostenvorschusses angefochten hat. Hätte der Beschwerdeführer bereits gegen den Zwischenentscheid des Handelsgerichts vom 20. März 2008 betreffend die Verweigerung der unentgeltlichen Rechtspflege Rechtsmittel erhoben, wäre der Beschwerdegegnerin im Verfahren vor Bundesgericht keine Parteistellung zugekommen und hätten ihr entsprechend weder die Gerichtskosten noch eine Parteientschädigung auferlegt werden können. Da sich das vorliegende Beschwerdeverfahren auf die Frage der unentgeltlichen Rechtspflege beschränkt, rechtfertigt es sich auch hier nicht, der Beschwerdegegnerin Kosten und Entschädigungen zu auferlegen (Art. 66 Abs. 1 Satz 2 sowie Art. 68 Abs. 1 und 2 BGG). Zudem konnte auf das Hauptbegehren des Beschwerdeführers nicht eingetreten werden. Ein Gesuch um Beiordnung eines unentgeltlichen Rechtsbeistands hat der Beschwerdeführer für das bundesgerichtliche Verfahren im Übrigen nicht gestellt (vgl. <ref-law>). Die Parteikosten werden daher wettgeschlagen.

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten, soweit sie sich gegen den Beschluss des Handelsgerichts des Kantons Zürich vom 5. Mai 2008 richtet.
2. Im Übrigen wird die Beschwerde gutgeheissen, der Beschluss des Kassationsgerichts vom 10. November 2008 wird aufgehoben und die Sache an die Vorinstanz zurückgewiesen.
3. Es werden keine Gerichtskosten erhoben.
4. Die Parteikosten werden wettgeschlagen.
5. Dieses Urteil wird den Parteien, dem Kassationsgericht des Kantons Zürich und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 14. April 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann