Sachverhalt:
A. Die A._ AG (Klägerin 1) und die B._ AG (Klägerin 2) sind in Zürich domiziliert, die C._ GmbH (Klägerin 3), die D._ GmbH (Klägerin 4), die E._ GmbH (Klägerin 5) und die F._ AG (Klägerin 6) sind in Deutschland ansässig. Die Klägerinnen stellen das Produkt M. her oder vertreiben es.
Die G._ GmbH (Beklagte) hat ihren Sitz in Deutschland. Sie ist Inhaberin des europäischen Patents X. Sie beansprucht dieses Patent für mehrere Vertragsstaaten.
B. Am 25. Mai 2005 stellten die Klägerinnen beim Handelsgericht des Kantons Zürich folgende Rechtsbegehren:
1. Der schweizerische Teil des europäischen Patents X. sei nichtig zu erklären,
eventualiter sei gerichtlich festzustellen, dass die Klägerinnen mit dem Produkt M. den schweizerischen Teil des europäischen Patents X. der Beklagten nicht verletzen oder verletzt haben.
2. Es sei gerichtlich festzustellen, dass die Klägerinnen mit dem Produkt M. weder den deutschen noch den französischen Teil des europäischen Patents X. verletzen oder verletzt haben,
insbesondere weil
a) das beklagtische Patent X. ungültig oder nicht durchsetzbar ist; oder
b) das Herstellen, Feilhalten, Vertreiben und in Verkehr bringen des Produktes M. durch die Klägerinnen weder in der Schweiz noch im Ausland das europäische Patent der Beklagten verletzt oder verletzt hat.
3. Es sei gerichtlich festzustellen, dass der Beklagten gegenüber den Klägerinnen keinerlei durchsetzbare Forderungen, insbesondere weder Schadenersatz-, Gewinnherausgabe- oder Genugtuungsansprüche im Zusammenhang mit dem klägerischen Produkt M. oder mit den beklagtischen Patenten oder Patentanteilen zustehen."
Die Beklagte schloss auf Nichteintreten bzw. Abweisung der Klage und erhob Widerklage im Wesentlichen mit den Rechtsbegehren, es sei den Klägerinnen 1, 2 und 5 zu verbieten, in der Schweiz bestimmte Produkte, insbesondere die unter der Bezeichnung M. vertriebenen, herzustellen, anzubieten, zu verkaufen oder anderweitig in Verkehr zu bringen, in die Schweiz einzuführen sowie aus der Schweiz auszuführen oder zu solchen Handlungen Dritter anzustiften, bei ihnen mitzuwirken oder ihre Begehung zu begünstigen (Ziffer 1), und die Klägerinnen 1, 2 und 5 seien für entsprechend patentverletzende Handlungen zur Rechnungslegung (Ziffer 2) sowie zu Schadenersatz oder Gewinnherausgabe (Ziffer 3) zu verpflichten.
Auf Antrag der Beklagten beschränkte das Handelsgericht das Verfahren mit Verfügung vom 30. September 2005 vorerst auf die Frage der örtlichen Zuständigkeit bzw. des Rechtsschutzinteresses.
C. Mit Beschluss vom 3. April 2006 trat das Handelsgericht auf die Klage der Klägerinnen 1 und 2 ein (Ziffer 1a); auf die Klage der Klägerinnen 3, 4 und 6 trat es nicht ein (Ziffer 1b). Auf die Klage der Klägerin 5 wurde bezüglich Rechtsbegehren 1 eingetreten, bezüglich Rechtsbegehren 2 nicht eingetreten und bezüglich Rechtsbegehren 3 insoweit eingetreten, als es um Forderungen aus Verletzung des schweizerischen Teils des Streitpatents geht, und nicht eingetreten insoweit, als es um Forderungen aus Verletzung ausländischer Teile des Streitpatents geht. Das Gericht führte aus, dass das LugÜ zur Anwendung gelangt. Zum Rechtsbegehren 1 stellte das Gericht fest, dass die Klägerinnen 3, 4 und 6 in der Schweiz am Markt nicht aufträten und auch nicht behaupteten, dass sie dies beabsichtigten, weshalb sie kein Rechtsschutzinteresse an der beantragten Feststellung der Patentnichtigkeit hätten. Die örtliche Zuständigkeit zur Beurteilung des Rechtsbegehrens 2 bejahte das Gericht für die Klägerinnen 1 und 2 mit der Begründung, sie hätten ihren Sitz in der Schweiz und <ref-law> schütze nicht den formell, sondern den materiell Beklagten. Die Zuständigkeit nach Art. 5 Ziffer 3 LugÜ verneinte das Gericht mit der Begründung, die Klägerinnen 1 und 2 könnten sich darauf nicht berufen, weil sie ihren Sitz in der Schweiz haben und die Klägerinnen 3-6 nicht, weil die Verletzung ausländischer Patente zur Diskussion stehe. Die Zuständigkeit gestützt auf Art. 6 Ziffer 1 LugÜ, auf die sich die Klägerinnen 3-6 beriefen, verneinte das Gericht. Für das Rechtsbegehren 3 bejahte das Gericht die Zuständigkeit nach Art. 5 Ziffer 3 LugÜ insoweit, als es um die Verletzung des schweizerischen Teils des europäischen Patents geht, wobei es das Feststellungsinteresse nur für die Klägerinnen 1, 2 und 5 bejahte. Aus <ref-law> bejahte das Gericht die örtliche Zuständigkeit für die Klägerinnen 1 und 2 sowohl für Ansprüche aus Verletzung des schweizerischen als auch aus Verletzung ausländischer Teile des Streitpatents.
D. Gegen den Beschluss des Handelsgerichts des Kantons Zürich vom 3. April 2006 haben sowohl die Beklagte wie die Klägerin 6 Berufung eingereicht. Die Beklagte stellt den Antrag, es sei Dispositiv-Ziffer 1a) des angefochtenen Entscheides aufzuheben und auf die Klage der Klägerinnen 1 und 2 bezüglich Rechtsbegehren 1 einzutreten, bezüglich Rechtsbegehren 2 nicht einzutreten und bezüglich Rechtsbegehren 3 insoweit einzutreten, als es um Forderungen aus Verletzung des schweizerischen Teils des Streitpatents geht, und nicht einzutreten insoweit, als es um Forderungen aus Verletzung ausländischer Teile des Streitpatents geht. Sie rügt, die Vorinstanz habe den Gerichtsstand für die Verletzung des deutschen und französischen Teils des Patents X. der Beklagten zu Unrecht bejaht.
E. Die Klägerinnen 1 und 2 beantragen die Abweisung der Berufung der Beklagten, soweit darauf einzutreten ist.

Das Bundesgericht zieht in Erwägung:
1. Die Berufung der Beklagten richtet sich gegen den selbständigen Zwischenentscheid über die Zuständigkeit, mit dem die Vorinstanz auf die Klage der Klägerinnen 1 und 2 vollumfänglich eingetreten ist. Sie ist gemäss Art. 49 OG grundsätzlich zulässig, da der Entscheid des Handelsgerichts des Kantons Zürich nicht durch ein ordentliches kantonales Rechtsmittel angefochten werden kann (Art. 48 Abs. 1 OG) und er die örtliche bzw. internationale Zuständigkeit betrifft, welche die Vorinstanz in Anwendung bundesrechtlicher Normen bzw. der Bestimmungen des Lugano-Übereinkommens (LugÜ; SR 0.275.11) bejaht hat (<ref-ruling> E. 2b S. 418 mit Verweisen). Da die übrigen Voraussetzungen ohne weiteres erfüllt sind, ist auf die Berufung einzutreten.
2. Die Vorinstanz hat ihre Zuständigkeit zur Beurteilung des Rechtsbegehrens 2 für die in der Schweiz domizilierten Klägerinnen 1 und 2 mit der Begründung bejaht, die Klägerinnen könnten sich zur Begründung der örtlichen Zuständigkeit auf ihren eigenen Wohnsitz berufen, da sie eine negative Feststellung verlangten und sich der umstrittene Anspruch daher materiell gegen sie richte, was die Zuständigkeit am allgemeinen Wohnsitzgerichtsstand der Klägerin nach <ref-law> begründe. Das Handelsgericht verneinte dabei vorweg, dass die ausschliessliche Zuständigkeit nach Art. 16 Ziffer 4 LugÜ auf das Klagebegehren 2 Anwendung finde.
2.1 Nach <ref-law> sind Personen, die ihren Wohnsitz im Hoheitsgebiet eines Vertragsstaats haben, ohne Rücksicht auf ihre Staatsangehörigkeit, vorbehaltlich der Vorschriften dieses Übereinkommens vor den Gerichten des Wohnsitzstaates zu verklagen. Der Wohnsitzgerichtsstand des Beklagten ist der zentrale Anknüpfungspunkt für die Anwendbarkeit des LugÜ überhaupt, während der Wohnsitz oder Sitz des Klägers dafür regelmässig unbeachtlich ist (<ref-ruling> E. 3.2 S. 744 mit Verweis; Gerhard Walter, Internationales Zivilprozessrecht der Schweiz, 3. Aufl. 2002, S. 176; Jan Kropholler, Europäisches Zivilprozessrecht, Kommentar zu EuGVO, Lugano-Übereinkommen und Europäischem Vollstreckungstitel, 8. Aufl. 2005, N. 9 f. vor Art. 2 EuGVO). Es handelt sich um die Konkretisierung der allgemeinen Regel "actor sequitur forum rei" (<ref-ruling> E. 4 S. 289). Unerheblich ist, ob der Ansprecher eine Leistungsklage oder der Anspruchsgegner eine negative Feststellungsklage erhebt, denn in beiden Fällen ist der Wohnsitz des Beklagten massgebend (Kropholler, a.a.O., N. 1 zu Art. 2 EuGVO). Der Klägergerichtsstand steht für negative Feststellungsklagen nicht zur Verfügung, woran der in <ref-ruling> publizierte Entscheid entgegen der Auffassung der Vorinstanz nichts ändert. In diesem Urteil hat das Bundesgericht für die ausschliesslich dem schweizerischen Recht bekannte Aberkennungsklage erkannt, dass es nicht darauf ankommen könne, ob der Gläubiger statt einer Forderungsklage den Weg der Betreibung wählt, und es daher <ref-law> nicht widerspreche, wenn ausnahmsweise auf die materielle Berechtigung statt der formellen Stellung im Prozess abgestellt werde (<ref-ruling> E. 5.3 S. 291 ff.). Aus der Begründung dieses Entscheids ergibt sich eindeutig, dass es ganz besonderer Umstände bedarf, um von der zentralen Anknüpfung an den Wohnsitz bzw. Sitz des im Verfahren formell Beklagten abzuweichen. Materielle Verhältnisse, welche die örtliche Zuständigkeit sinnvoll oder zur Verhinderung einer "weiteren Prozessverzettelung" wünschbar erscheinen lassen, vermögen die Zuständigkeit am gesetzlich nicht vorgesehenen Klägergerichtsstand jedenfalls nicht zu begründen.
2.2 Die Vorinstanz hat die Tragweite von <ref-law> verkannt, indem sie ihre örtliche Zuständigkeit zur Beurteilung der negativen Feststellungsklage in Ziffer 2 der Klagebegehren gestützt auf den Sitz der Klägerinnen in der Schweiz bejahte. Zur Beurteilung der begehrten Feststellung, dass die Klägerinnen 1 und 2 weder den deutschen noch den französischen Teil des europäischen Patents X. der Beklagten verletzen, sind die Gerichte in der Schweiz ohne Einverständnis der Beklagten nicht zuständig. Folgerichtig ist die Vorinstanz auch unzuständig zur im Begehren 3 beantragten Feststellung, dass der Beklagten aus der Verletzung des deutschen oder französischen Teils des Patents X. keine Forderungen zustehen. Bei dieser Sachlage kann offenbleiben, ob die Vorinstanz zutreffend von der Annahme ausgegangen ist, die zwingende Zuständigkeit gemäss Art. 16 Ziffer 4 LugÜ stehe ihrer Zuständigkeit zur Feststellung (nicht erfolgter) Verletzung ausländischer Patente auch dann nicht entgegen, wenn vorfrageweise die Feststellung der Patentnichtigkeit verlangt werde. Diese Auffassung hat die Vorinstanz im angefochtenen Beschluss vertreten, bevor der EuGH in der Rechtssache C-4/03 am 13. Juli 2006 entschieden hat, dass die ausschliessliche Zuständigkeitsregel von Art. 16 Ziffer 4 EuGVÜ/LugÜ alle Arten von Rechtsstreitigkeiten über die Eintragung oder die Gültigkeit eines Patents unabhängig davon betrifft, ob die Frage klageweise oder einredeweise aufgeworfen wird.
3. Soweit die Klägerinnen in der Berufungsantwort die Ansicht vertreten, die Zuständigkeit schweizerischer Gerichte könnte am deliktischen Handlungsort begründet sein, verkennen sie die Tragweite von Art. 5 Ziffer 3 LugÜ. Nach dieser Bestimmung kann eine Person mit Wohnsitz in einem Vertragsstaat in einem anderen Vertragsstaat vor dem Gericht des Ortes verklagt werden, an dem das schädigende Ereignis eingetreten ist, wenn eine unerlaubte bzw. dieser gleichgestellte Handlung oder Ansprüche aus einer solchen Handlung den Gegenstand des Verfahrens bilden. Diese Zuständigkeit beruht auf der Erwägung, dass hier eine besondere Nähe zum Streitgegenstand besteht und das Gericht am Ort, an dem das schädigende Ereignis eingetreten ist, am besten in der Lage ist, die erforderlichen Beweise zu erheben und den Streit zu entscheiden (Jan Kropholler, Europäisches Zivilprozessrecht, Kommentar zu EuGVO, Lugano-Übereinkommen und Europäischem Vollstreckungstitel, 8. Aufl. 2005, N. 73 zu Art. 5 EuGVO; Hélène Gaudemet-Tallon, Compétences et exécution des jugements en Europe, 3. Aufl. 2002, S. 125 Rz. 171). Als eingetreten wird das schädigende Ereignis nach der hier massgebenden Praxis des EuGH sowohl am Ort der Vornahme der deliktischen Handlung wie am Ort des Erfolgs anerkannt (<ref-ruling> E. 4a S. 348; Gaudemet-Tallon, a.a.O., S. 172 Rz. 215). Für die Verletzung ausländischer Patente käme höchstens der Handlungsort als Deliktsort in Betracht. Da eine Patentverletzung eine Benutzungshandlung auf dem Gebiet des Staates, für den das Patent erteilt wurde, voraussetzt, kann nämlich der Erfolgsort als Ort, an dem die Rechtsgutverletzung eintritt, immer nur in diesem Staat liegen. Gegen die Zuständigkeit der Gerichte am Handlungsort bei der Verletzung ausländischer Patente im Inland spricht jedoch die Erwägung, dass die Patentverletzung weder im Gerichtsstaat erfolgt ist noch dessen materielles Recht zur Anwendung kommt, womit es an der für Art. 5 Ziffer 3 LugÜ erforderlichen besonderen Nähe zum Streitgegenstand fehlt (Klaus Grabinski, Zur Bedeutung des Europäischen Gerichtsstands- und Vollstreckungsübereinkommens [Brüsseler Übereinkommens] und des Lugano-Übereinkommens in Rechtsstreitigkeiten über Patentverletzungen, in: GRUR Int. 2001 S. 201/204 f.; vgl. auch Pierre Véron, Trente ans d'application de la Convention de Bruxelles à l'action en contrefaçon de brevet d'invention, in: Journal du Droit International [Clunet] 2001 S. 805/826 f.).
4. Die Berufung ist gutzuheissen und der angefochtene Beschluss ist gemäss dem Antrag der Beklagten abzuändern. Die Gerichtsgebühr ist bei diesem Verfahrensausgang den Klägerinnen 1 und 2 zu auferlegen, welche mit ihren Begehren unterlegen sind. Sie haben der anwaltlich vertretenen Beklagten deren Parteikosten zu ersetzen. Gerichtsgebühr und Parteientschädigung bemessen sich nach dem Streitwert, den die Vorinstanz mit mehr als 1 Million SFr. bemisst.

Demnach erkennt das Bundesgericht:
1. Die Berufung wird gutgeheissen, Dispositiv-Ziffer 1a des angefochtenen Beschlusses des Handelsgerichts des Kantons Zürich vom 3. April 2006 wird aufgehoben und wie folgt neu gefasst:
1. a) Auf die Klage der Klägerinnen 1 und 2 wird bezüglich Rechtsbegehren 1 eingetreten, bezüglich Rechtsbegehren 2 nicht eingetreten und bezüglich Rechtsbegehren 3 insoweit eingetreten, als es um Forderungen aus Verletzung des schweizerischen Teils des Streitpatents geht, und nicht eingetreten insoweit, als es um Forderungen aus Verletzung ausländischer Teile des Streitpatents geht."
2. Die Sache wird zur Neuverlegung der Kosten des kantonalen Verfahrens an die Vorinstanz zurückgewiesen.
3. Die Gerichtsgebühr von Fr. 10'000.-- wird den Klägerinnen 1 und 2 unter solidarischer Haftbarkeit auferlegt.
4. Die Klägerinnen 1 und 2 haben die Beklagte für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 12'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 23. Oktober 2006
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: