Sachverhalt: A. A.a X._ SA (Beschwerdeführerin) ist eine Aktiengesellschaft mit Sitz in Genf. X._ Ltd. (Beschwerdegegnerin) ist eine Gesellschaft englischen Rechts mit Sitz in Fulham, London. A.b Die Parteien haben am 28. April 2004 ein "Franchise Agreement" und ein diesem angehängtes "Supply Agreement" abgeschlossen. Gemäss diesen Vereinbarungen wird die Beschwerdeführerin als Franchisenehmerin in der Schweiz, Liechtenstein, Italien, Monaco, Österreich und der Slowakei tätig und die Beschwerdegegnerin beliefert sie mit den für diese Tätigkeit benötigten Produkten. B. Dieses Vertragsverhältnis wurde von der Beschwerdegegnerin am 9. April 2008 gekündigt. Die Beschwerdeführerin akzeptierte diese Kündigung nicht und klagte beim Handelsgericht des Kantons Zürich gegen die Beschwerdegegnerin mit dem Rechtsbegehren, es "sei festzustellen, dass die Kündigung des Franchise and Supply Agreements ungültig ist und das Vertragsverhältnis somit fortgeführt wird"; eventualiter sei die Beschwerdegegnerin zu verpflichten, der Beschwerdeführerin Fr. 400'000.-- zu bezahlen (Ziffer 1 des Rechtsbegehrens). Darüber hinaus wirft die Beschwerdeführerin der Beschwerdegegnerin verschiedene Vertragsverletzungen (u.a. fehlende Unterstützung im Rechnungs- und Bestellwesen, fehlende Unterstützung im Vertrieb, Verweigerung der Zusammenarbeit) vor, wofür sie Schadenersatz im Betrag von Fr. 2.5 Mio. verlangt (Ziffer 2 des Rechtsbegehrens). Das Handelsgericht des Kantons Zürich erwog, dass es für alle Rechtsbegehren der Beschwerdeführerin an einem Gerichtsstand im Sinne von Art. 5 Ziff. 1 des Lugano-Übereinkommens vom 16. September 1988 über die gerichtliche Zuständigkeit und die Vollstreckung gerichtlicher Entscheidungen in Zivil- und Handelssachen (LugÜ; SR 0.275.11) in Zürich fehle, weshalb es mit Beschluss vom 24. April 2009 mangels Zuständigkeit auf die Klage nicht eintrat. C. Mit Beschwerde in Zivilsachen beantragt die Beschwerdeführerin dem Bundesgericht, es sei der Beschluss des Handelsgerichts des Kantons Zürich vom 24. April 2009 aufzuheben und die Zuständigkeit des Handelsgerichts festzustellen. Eventualiter sei der Beschluss des Handelsgerichts aufzuheben und die Streitsache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. D. Mit Verfügung vom 23. Juni 2009 erteilte das Bundesgericht der Beschwerde aufschiebende Wirkung.