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.

Erwägungen:
1. 1.1 Mit der Gutheissung der Unzuständigkeitseinrede der Beschwerdegegnerin hat die Vorinstanz, ein Fachgericht für handelsrechtliche Streitigkeiten, als einzige kantonale Instanz (<ref-law>) einen Endentscheid gefällt (<ref-law>). Hiergegen ist in der vorliegenden zivilrechtlichen Vermögensstreitigkeit (<ref-law>) mit einem Fr. 30'000.-- übersteigenden Streitwert (<ref-law>) die Beschwerde in Zivilsachen gegeben.
1.2 Nach <ref-law> ist in der Beschwerdeschrift in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Soweit eine Verletzung von Bundesrecht oder Völkerrecht geltend gemacht wird, wendet das Bundesgericht das Recht zwar von Amtes wegen an (<ref-law>). Es überprüft aber grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 1.4.1 S. 254; <ref-ruling> E. 2.2 S. 550).
2. Die Beschwerdeführerin rügt eine Verletzung von <ref-law>.
2.1 Sie bringt vor, für die Bestimmung des nach <ref-law> massgeblichen Anknüpfungspunktes sei die streitbefangene Primärpflicht massgebend. Demgegenüber habe es der EuGH in ständiger Rechtsprechung abgelehnt, an die vertragscharakteristische Leistung anzuknüpfen. Mit dem zentralen Argument, es sei für das Begehren auf Feststellung, dass die sich aus dem Vertragsverhältnis ergebenden Pflichten der beklagten Partei weiterhin wirksam sind, auf den vertraglichen Anspruch abzustellen, auf den es der klagenden Partei hauptsächlich ankommt, nämlich die in Newtown (Wales) zu erfüllende Warenlieferung der Franchisegeberin, knüpfe die Vorinstanz fälschlicherweise an die vertragscharakteristische Leistung an. Diese Anknüpfung sei unzutreffend, weil nach <ref-law> die streitbefangene Primärpflicht der entscheidende Anknüpfungspunkt sei.
Streitbefangene Primärpflicht, so die Beschwerdeführerin weiter, sei die Weiterführung des Franchise Agreements. Auch bei einem Feststellungsbegehren richte sich die Anknüpfung der Zuständigkeit nach der verletzten vertraglichen Pflicht. Die von der Vorinstanz erwähnte Diskussion in der Lehre über den Erfüllungsort bei Feststellungsklagen sei nur dann relevant, wenn sich aus dem Feststellungsbegehren keine vertragliche Pflicht ableiten lasse. Diese Unsicherheit bestehe aber im vorliegenden Fall nicht; die Beschwerdegegnerin solle gerade verpflichtet werden, ihre vertraglichen Pflichten aus dem Franchise Agreement zu erfüllen. In der Folge äussert sich die Beschwerdeführerin zu den vertraglichen Pflichten aus einem Franchise Agreement im Allgemeinen und dem zu beurteilenden Vertrag im Besonderen. Dabei handle es sich um einen klassischen Franchisevertrag, welcher der Beschwerdegegnerin als Franchisegeberin verschiedene vertragliche Pflichten auferlege. Es gehe im vorinstanzlichen Verfahren im Kern um den Antrag der Beschwerdeführerin, diese vertraglichen Verpflichtungen weiterzuführen.
Anknüpfungspunkt für die Beurteilung der Zuständigkeit sei nicht die Lieferverpflichtung, sondern das Franchise Agreement. Die Verpflichtungen der Beschwerdegegnerin aus dem Franchise Agreement, das sich begriffsnotwendig auf ein im Vertrag definiertes Vertragsgebiet beziehe, könnten nur im Vertragsgebiet erfüllt werden. Zudem müsse und könne die Beschwerdeführerin ihre Verpflichtung, im Vertragsgebiet eine bestimmte Anzahl von Läden zu betreiben, nur im Vertragsgebiet erfüllen, das gemäss Ziff. 2 des Franchise Agreement die Schweiz, Liechtenstein, Italien, Monaco, Österreich und die Slowakei erfasse. Massgebend für die Bestimmung des Erfüllungsorts innerhalb dieser Ländergruppe sei die Frage, wo die Hauptverwaltung des Franchisenehmers angesiedelt sei. Die Beschwerdeführerin habe ihren "tatsächlichen Sitz" in Zürich, das gesamte Bestell- und Abrechnungswesen erfolge über Zürich und auch das Marketing werde zentral über den Hauptsitz in Zürich geführt, was deutlich für einen Erfüllungsort in der Schweiz spreche. Dass der Vertrag in Zürich erfüllt werde, entspreche im Übrigen dem Verständnis der Parteien. So sei in allen Katalogen der Beschwerdegegnerin bis Frühjahr 2008 die Zürcher Adresse als Hauptsitz der Beschwerdeführerin aufgeführt worden, die Beschwerdegegnerin habe ihre Tageskorrespondenz sowie die Rechnungen für alle Läden im Vertragsgebiet an diese Adresse gesandt, die Kasse und das Kasseninternetsystem würden von Zürich aus gewartet und gehostet, das Lagerhaus der Beschwerdeführerin sei in Zürich, die Betriebsfahrzeuge dort angemeldet und das gesamte operative Geschäft befinde sich in Zürich. Schliesslich sei auch der für einen beschränkten Zeitraum beschäftigte Geschäftsführer in Zürich angestellt gewesen und die wenigen Besuche der Beschwerdegegnerin bei der Beschwerdeführerin hätten in den Geschäftsräumen in Zürich stattgefunden. Im Übrigen sei auch das Franchise Agreement an diesem Ort unterzeichnet worden. Aus all diesen Gründen, die von der Vorinstanz nicht gewürdigt worden seien, ergebe sich eine internationale Zuständigkeit in der Schweiz und eine örtliche Zuständigkeit in Zürich.
2.2 Wenn ein Vertrag oder Ansprüche aus einem Vertrag den Streitgegenstand bilden, ermöglicht <ref-law> dem Kläger, alternativ zum allgemeinen Wohnsitzgerichtsstand (<ref-law>), den Beklagten vor dem Gericht des Ortes zu verklagen, an dem die Verpflichtung erfüllt worden ist oder zu erfüllen wäre. Zur Bestimmung des Erfüllungsorts ist nicht jede beliebige vertragliche Verpflichtung massgebend, sondern nur jene, die dem vertraglichen Anspruch entspricht, auf den der Kläger seine Klage stützt. Macht er Ansprüche auf Schadenersatz geltend oder beantragt er die Auflösung des Vertrags aus Verschulden der anderen Partei, so ist auf die vertragliche Verpflichtung abzustellen, deren Nichterfüllung zur Begründung dieser Ansprüche behauptet wird (BGE 4A_115/2009 vom 11. Juni 2009 E. 3.1; <ref-ruling> E. 4a S. 189 f. mit Hinweisen auf die Rechtsprechung des EuGH). Massgebend ist demnach immer die strittige Primärpflicht und nicht etwa die aus der Kündigung, Wandelung, Schadenersatzforderung wegen Nicht- oder Schlechterfüllung, Rückabwicklung des Vertrags etc. hervorgehende Sekundärpflicht (BGE 4A_115/2009 vom 11. Juni 2009 E. 3.2 mit Hinweisen).
Dies verkennt die Beschwerdeführerin, wenn sie vorträgt, im Falle einer Klagehäufung dürfe das für einen Anspruch zuständige Gericht auch über die anderen Ansprüche entscheiden, die in verschiedenen Staaten zu erfüllen sind. Die Vorinstanz hat unter Hinweis auf die Rechtsprechung des EuGH vielmehr zutreffend erwogen, dass das für einen Anspruch zuständige Gericht grundsätzlich nicht auch über die anderen Ansprüche entscheiden darf, selbst wenn sich die verschiedenen Ansprüche aus demselben Vertrag ergeben.
Das Bundesgericht hat zudem eine Ausdehnung des Gerichtsstands des Erfüllungsorts im Sinne der Annahme einer Zuständigkeit am Ort der Erfüllung einer als solcher nicht umstrittenen, beliebigen vertraglichen Hauptleistung nach Wahl des Klägers in einem neueren Entscheid abgelehnt (BGE 4A_115/2009 vom 11. Juni 2009 E. 3.4). Die Beschwerdeführerin legt jedoch nicht dar, welche umstrittene Verpflichtung in Zürich zu erfüllen gewesen wäre, sondern beschränkt sich vielmehr darauf, die verschiedenen Verpflichtungen aus dem Franchise und dem Supply Agreement aufzulisten und vorzubringen, streitbefangene Primärpflicht sei die Weiterführung des Franchisesystems als Ganzes. Damit lässt sie ausser Acht, dass es nach <ref-law> auf den Erfüllungsort nicht irgendeiner, sondern der umstrittenen Verpflichtung ankommt (BGE 4A_115/2009 vom 11. Juni 2009 E. 3.4). Es lässt sich den Ausführungen der Beschwerdeführerin aber nicht entnehmen, auf welche konkrete vertragliche Pflicht sich ihr Feststellungsbegehren stützt, deren Erfüllungsort in Zürich liegen würde. Auch aus den verschiedenen von ihr vorgebrachten tatsächlichen Bezugspunkten zu Zürich ("tatsächlicher Sitz", Bestell- und Abrechnungswesen, Marketing, Kasse, Lagerhaus, Betriebsfahrzeuge, Ort der Vertragsunterzeichnung etc.) lässt sich kein Erfüllungsort für eine vertragliche Pflicht ableiten.
Ebenso wenig hat die Beschwerdeführerin aufgezeigt, dass die von ihr behauptete Unwirksamkeit der Kündigung darauf beruhe, dass sie eine bestimmte Vertragspflicht entgegen der Behauptung der Beschwerdegegnerin gar nicht verletzt habe. Im Übrigen untersteht die in der Klageschrift im Zusammenhang mit der Kündigung erwähnte umstrittene Zahlungsverpflichtung der Beschwerdeführerin englischem Recht, das von einer Bringschuld ausgeht (ALEXANDER R. MARKUS, Tendenzen beim materiellrechtlichen Vertragserfüllungsort im internationalen Zivilverfahrensrecht, 2009, S. 35; YVES DONZALLAZ, La Convention de Lugano, Bd. III, 1998, Rz. 4684), weshalb auch diese Verpflichtung nicht in Zürich, sondern in London zu erfüllen wäre. Die Rüge, die Vorinstanz habe den Grundsatz der Rechtsanwendung von Amtes wegen (iura novit curia) verletzt, indem sie weder selbst Abklärungen zum englischen Recht getroffen noch die Beschwerdeführerin zu einer entsprechenden Stellungnahme eingeladen habe, stösst ins Leere.
2.3 Zusammenfassend ist ein Erfüllungsort in Zürich nach <ref-law> für die Feststellungsklage der Beschwerdeführerin nicht gegeben. Auf das eventualiter erhobene Forderungsbegehren über Fr. 400'000.-- (Ziffer 1 des Rechtsbegehrens) sowie das zusätzlich geltend gemachte Schadenersatzbegehren über Fr. 2.5 Mio. (Ziffer 2 des Rechtsbegehrens), für welche die Vorinstanz einen Gerichtsstand ebenfalls verneint hat, geht die Beschwerdeführerin vor Bundesgericht nicht ein. Die Vorinstanz hat weder "fundamentale Grundsätze von <ref-law>" noch <ref-law> verletzt, wenn sie auf die Klage mangels Zuständigkeit nicht eingetreten ist.
3. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 20'000.-- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 22'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 20. August 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann