Sachverhalt:
A. A.a Die X._ AG (Klägerin, Beschwerdeführerin) beauftragte die Y._ AG (Beklagte, Beschwerdegegnerin), mit Lastwagen 33 Euro-Paletten Zigaretten vom Werk der ZA._ SA zur ZB._ BV nach Q._ in den Niederlanden zu transportieren. Die Beklagte zog ihrerseits die R._ BV mit Sitz in S._ (Niederlande) als Unterfrachtführerin bei, deren Chauffeur die Zigaretten am 8. Dezember 2004 lud und aus der Schweiz - vorerst ohne Verzollung - in die Europäische Union ausführte. Der Lastwagenchauffeur machte in der Nacht vom 8. auf den 9. Dezember 2004 im Hafengebiet von Antwerpen auf einem unbewachten Gelände einen Halt, um zu schlafen. Dort wurden die Zigaretten vermutlich gestohlen und nicht mehr aufgefunden.
Die belgische Zollbehörde stellte daraufhin fest, dass die Zigaretten nicht wie vorgesehen ordnungsgemäss nach den Niederlanden wieder ausgeführt worden waren und diese daher als in den freien belgischen Warenverkehr gebracht gälten. Sie erhob daher Zölle und Einfuhrabgaben von EUR 1'514'250.66.
A.b Am 9. September 2005 reichte die Y._ AG beim Amtsgericht Breda (Niederlande) Klage ein auf Feststellung, dass sie der X._ AG, der ZA._ SA, der ZB._ BV, der TC._ BV, der TD._ BV sowie der R._ BV aus dem Zigarettendiebstahl nicht hafte, eventualiter dass sie für den Schaden aus diesem Diebstahl nach Art. 23 - 25 des Übereinkommens über den Beförderungsvertrag im internationalen Strassengüterverkehr (CMR) nur beschränkt hafte.
B. B.a Am 20. Mai 2009 beantragte die X._ AG dem Bezirksgericht Liestal hauptsächlich, die Y._ AG sei zu verpflichten, ihr EUR 1'514'250.66 nebst 9.6 % Zins jährlich seit 9. September 2008 auf EUR 964'290.65 und 0.8 % monatlich auf EUR 234'545.85 sowie zusätzlich Fr. 1'665.80 Betreibungskosten zu bezahlen.
Mit Urteil vom 9. Juni 2011 trat das Bezirksgericht auf die Klage nicht ein. Das Gericht kam zum Schluss, die Streitigkeit sei nach <ref-law> in Breda rechtshängig.
B.b Das Kantonsgericht Basel-Landschaft wies die Berufung der Klägerin gegen dieses Urteil mit Entscheid vom 21. Februar 2012 ab.
C. Mit Beschwerde in Zivilsachen stellt die Klägerin die Rechtsbegehren, der Entscheid des Kantonsgerichts Basel-Landschaft vom 21. Februar 2012 sei aufzuheben und die Sache sei zur Neubeurteilung an das Bezirksgericht Liestal zurückzuweisen; eventualiter sei das Bezirksgericht Liestal anzuweisen, das Verfahren bis zum Vorliegen eines rechtskräftigen Entscheids eines niederländischen Gerichts im Verfahren Case Docket no: uuu._ zu sistieren.
Die Beschwerdegegnerin schliesst in ihrer Antwort auf Abweisung der Beschwerde, soweit darauf einzutreten sei.
Die Parteien haben ohne amtliche Anordnung eines zweiten Schriftenwechsels repliziert und dupliziert.

Erwägungen:
1. Die Streitigkeit betrifft eine Zivilsache (<ref-law>) mit einem Streitwert über Fr. 30'000.-- (<ref-law>). Der angefochtene Endentscheid (<ref-law>) ist von einem oberen kantonalen Gericht als Rechtsmittelinstanz erlassen (<ref-law>) und von der mit ihren Anträgen unterlegenen Partei (<ref-law>) fristgerecht (Art. 100 Abs. 1 i.V.m. <ref-law>) angefochten worden. Auf die Beschwerde ist unter Vorbehalt zulässiger und hinreichend begründeter Anträge und Rügen (Art. 42 Abs. 1 und Art. 106 Abs. 2 BGG) einzutreten.
2. In ihrem Eventualantrag begehrt die Beschwerdeführerin, das erstinstanzliche Gericht sei anzuweisen, das Verfahren zu sistieren. Im angefochtenen Urteil finden sich keine Feststellungen und die Beschwerdeführerin weist nicht nach, dass sie diesen Antrag schon vor Kantonsgericht gestellt hätte. Der Antrag - mit dem die Beschwerdeführerin nicht bloss weniger, sondern etwas anderes verlangt als mit ihrem Hauptantrag - hat daher als neu zu gelten. Neue Begehren sind vor Bundesgericht ausgeschlossen (<ref-law>). Der Antrag ist unzulässig und es ist darauf nicht einzutreten.
3. Die Parteien sind sich zu Recht darüber einig, dass im vorliegenden Fall das Übereinkommen vom 19. Mai 1956 über den Beförderungsvertrag im internationalen Strassengüterverkehr (CMR; SR 0.741.611) anwendbar ist. Das Übereinkommen gilt für jeden Vertrag über die entgeltliche Beförderung von Gütern auf Strassen, wenn der Ort der Übernahme des Gutes und der für die Ablieferung vorgesehene Ort in zwei verschiedenen Staaten liegen und wenn mindestens der eine Vertragsstaat ist (<ref-law>). Die Beschwerdeführerin rügt, die Vorinstanzen hätten <ref-law> falsch ausgelegt und seien deshalb zu Unrecht auf ihre Leistungsklage nicht eingetreten. Sie bestreitet zunächst, dass eine negative Feststellungsklage nach <ref-law> überhaupt zulässig sei und bringt sinngemäss vor, das in den Niederlanden von der Beklagten befasste Gericht hätte auf deren Klage gar nicht eintreten dürfen. Sie rügt sodann, die Vorinstanz habe zu Unrecht Identität zwischen der in den Niederlanden hängigen negativen Feststellungsklage der Beklagten und ihrer Forderungsklage angenommen sowie zu Unrecht die Vollstreckbarkeit der negativen Feststellungsklage bejaht.
3.1 Für die Auslegung von Normen in internationalen Verträgen sind die Art. 31 ff. des Wiener Übereinkommens vom 23. Mai 1969 über das Recht der Verträge (Wiener Übereinkommen, VRK; SR 0.111) massgebend. Danach ist ein Vertrag nach Treu und Glauben in Übereinstimmung mit der gewöhnlichen, seinen Bestimmungen in ihrem Zusammenhang zukommenden Bedeutung und im Lichte seines Zieles und Zweckes auszulegen (Art. 31 Abs. 1 VRK). Der Wortlaut einer Vertragsnorm in seiner gewöhnlichen Bedeutung und im systematischen Zusammenhang des Vertrags ist danach ebenso massgebend wie die beim Abschluss des Vertrags getroffenen Übereinkünfte (Art. 31 Abs. 2 VRK) und die spätere Übung bei der Anwendung des Vertrags, sofern daraus eine Übereinstimmung der Vertragsparteien über seine Auslegung hervorgeht (Art. 31 Abs. 3 lit. b VRK). In diesem Rahmen ist das Verständnis der Bestimmungen, wie sie in Urteilen der Gerichte anderer Vertragsstaaten zum Ausdruck kommt, zu berücksichtigen. Die Vorinstanz hat insofern zutreffend die zwei gleichentags ergangenen Urteile des deutschen Bundesgerichtshofs vom 20. November 2003, auf die sich die Beschwerdeführerin beruft (BGH I ZR 102/02 und I ZR 294/02), ebenso berücksichtigt wie das Urteil des österreichischen Obersten Gerichtshofs vom 17. Februar 2006 (OGH 10 Ob 147/05y) und das Urteil des englischen Court of Appeal vom 23. Januar 2001 ([2001] EWCA Civ 61), welche zur Auslegung von <ref-law> ergangen sind.
3.2 Nach <ref-law> kann der Kläger, unter Vorbehalt einer Gerichtsstandsvereinbarung (zugunsten eines Gerichts eines Vertragsstaats), wegen aller Streitigkeiten aus einer diesem Übereinkommen unterliegenden Beförderung die Gerichte eines Staates anrufen, auf dessen Gebiet (a) der Beklagte seinen gewöhnlichen Aufenthalt, seine Hauptniederlassung oder die Zweigniederlassung oder Geschäftsstelle hat, durch deren Vermittlung der Beförderungsvertrag geschlossen worden ist, oder (b) der Ort der Übernahme des Gutes oder der für die Ablieferung vorgesehene Ort liegt. Andere Gerichte können nicht angerufen werden.
<ref-law> lautet: "Ist ein Verfahren bei einem nach Absatz 1 zuständigen Gericht wegen einer Streitigkeit im Sinne des genannten Absatzes anhängig oder ist durch ein solches Gericht in einer solchen Streitsache ein Urteil erlassen worden, so kann eine neue Klage wegen derselben Sache zwischen denselben Parteien nicht erhoben werden, es sei denn, dass die Entscheidung des Gerichtes, bei dem die erste Klage erhoben worden ist, in dem Staat nicht vollstreckt werden kann, in dem die neue Klage erhoben wird."
In den Originalsprachen Französisch und Englisch:
"Lorsque dans un litige visé au par. 1 du présent article une action est en instance devant une juridiction compétente aux termes de ce paragraphe, ou lorsque dans un tel litige un jugement a été prononcé par une telle juridiction, il ne peut être intenté aucune nouvelle action pour la même cause entre les mêmes parties à moins que la décision de la juridiction devant laquelle la première action a été intentée ne soit pas susceptible d'être exécutée dans le pays où la nouvelle action est intentée."
"Where in respect of a claim referred to in paragraph 1 of this article an action is pending before a court or tribunal competent under that paragraph, or where in respect of such a claim a judgement has been entered by such a court or tribunal no new action shall be started between the same parties on the same grounds unless the judgement of the court or tribunal before which the first action was brought is not enforceable in the country in which the fresh proceedings are brought."
3.3 <ref-law> schliesst entgegen der Ansicht der Beschwerdeführerin die negative Feststellungsklage nicht aus. Danach gelten die Zuständigkeitsbestimmungen für sämtliche Streitigkeiten aus dem CMR unterliegenden Verträgen ("Pour tous litiges auxquelles donnent lieu les transports soumis à la présente Convention") und nicht nur für die Haftpflicht des Frachtführers. Die Zuständigkeit knüpft sodann an die Parteirolle im Prozess an und entgegen der Auffassung der Beschwerdeführerin nicht an die Gläubigerstellung nach materiellem Recht, wenn nach dem Wortlaut der Norm "der Kläger ... die Gerichte ... anrufen" kann ("le demandeur peut saisir ... les juridictions" bzw. "the plaintiff may bring an action in any court or tribunal").
Für einen - impliziten - Ausschluss negativer Feststellungsklagen durch <ref-law> überhaupt ergeben sich entgegen der Ansicht der Beschwerdeführerin weder aus der Systematik der Bestimmungen irgendwelche Anhaltspunkte noch liegt eine solche Ansicht den Entscheiden des deutschen Bundesgerichtshofs vom 20. November 2003 (BGH I ZR 102/02 und I ZR 294/02) zugrunde. Darin wird vielmehr die Zulässigkeit der - je früher eingereichten - negativen Feststellungsklage ausdrücklich bejaht, jedoch (analog der Praxis nach dem internen deutschen Recht, wonach das Rechtsschutzinteresse an einer negativen Feststellungsklage entfällt, wenn eine entsprechende Leistungsklage eingereicht wird) der Vorrang der Leistungsklage vor einer hängigen negativen Feststellungsklage auch für Klagen aus Verträgen bejaht, die dem CMR unterstehen. Zur Begründung wird angeführt, eine negative Feststellungsklage begründe die Einrede der Rechtshängigkeit im Sinne von <ref-law> nicht, weil dem Anspruchsteller das Wahlrecht nach <ref-law> nicht entzogen werden dürfe (so auch ROLF HERBER/HENNING PIPER, Internationales Strassentransportrecht, München 1996, N. 26 zu <ref-law>). Die Beschwerdeführerin belegt sodann nicht, dass der angebliche Wille der Parteien des Übereinkommens, negative Feststellungsklagen überhaupt auszuschliessen, aus Dokumenten beim Vertragsschluss abgeleitet werden könnte.
Es ist davon auszugehen, dass die Beklagte gestützt auf <ref-law> vor einem zuständigen Gericht in den Niederlanden eine Klage eingereicht hat, mit der sie die Feststellung begehrt, dass sie der Klägerin (sowie weiteren Parteien) aus dem Zigarettendiebstahl nicht haftet, aus dem die Klägerin im vorliegenden Verfahren ihre Forderung ableitet. Es stellt sich allein die Frage, ob die Einrede der Rechtshängigkeit nach <ref-law> begründet ist.
3.4 Die Einrede der Rechtshängigkeit nach <ref-law> setzt zunächst voraus, dass dieselbe Sache zwischen denselben Parteien vor dem Gericht eines anderen Vertragsstaats hängig ist. Während vorliegend nicht umstritten ist, dass sich vor dem Gericht der Niederlande dieselben Parteien gegenüberstehen, bestreitet die Beschwerdeführerin, dass dieselbe Sache dort streitig ist. Sie begründet ihren Standpunkt im Wesentlichen im Sinne der Urteile des deutschen BGH aus dem Jahre 2003, die dem CMR eine Wertung über die Wahlmöglichkeiten des Forderungsgläubigers entnehmen, welche zum Ausschluss der Einrede der Rechtshängigkeit führt, wenn im hängigen Verfahren derselbe Anspruch Gegenstand einer negativen Feststellungsklage bildet.
Die Praxis des deutschen BGH ist in der Literatur umstritten (vgl. KLAUS DEMUTH, in: Thume [Hrsg.], Kommentar zur CMR, 2. Aufl., Frankfurt a.M. 2007, N. 58 zu <ref-law>; INGO KOLLER, Transportrecht, 7. Aufl., München 2010, N. 8 zu <ref-law>). Der österreichische Oberste Gerichtshof (Urteil des OGH 10 Ob 147/05y vom 17. Februar 2006) und der englische Court of Appeal (Urteil vom 23. Januar 2001, [2001] EWCA Civ 61) haben anders entschieden. Deren Ansicht kann die überzeugenderen Argumente für sich beanspruchen. So geht es allgemein um dieselbe Sache, wenn der Schuldner die Feststellung beansprucht, dass er aus einem bestimmten Ereignis nichts schulde und der Gläubiger aus demselben Sachverhalt eine Forderung einklagt. Dass es sowohl in den Niederlanden wie im vorliegenden Verfahren um die Ersatzpflicht der Beklagten aus dem Schaden geht, den der Zigarettendiebstahl verursacht hat, ist unbestritten. Gerade im internationalen Verhältnis, in dem unterschiedliche prozessuale Regelungen der Vertragsstaaten gelten, müssen über die Zuständigkeit - wozu die Rechtshängigkeit gehört - einfache und praktikable Regeln gelten. Eine Regelung, welche die negative Feststellungsklage grundsätzlich zulässt, jedoch der Leistungsklage in der gleichen Sache den Vorrang gewährt, führt zu Abgrenzungsfragen, wenn die Rechtshängigkeit oder die Rechtskraft in unterschiedlichen Prozessordnungen unterschiedlich definiert wird. Dies würde dem Ziel, sich widersprechende Urteile aus verschiedenen Vertragsstaaten zu verhindern, entgegenwirken (vgl. DEMUTH, a.a.O., N. 58 zu <ref-law>; KOLLER, a.a.O., N. 8 zu <ref-law> FN 93).
Es ist überdies, wie die Beschwerdeführerin mit ihrer Argumentation selbst beweist, nicht sehr folgerichtig, zwar die negative Feststellungsklage im Rahmen von <ref-law> grundsätzlich zuzulassen, sie jedoch mit der Begründung der eingeschränkten Wahlmöglichkeit nach dieser Bestimmung dennoch wieder auszuschliessen, sobald eine identische Leistungsklage eingereicht wird. Das CMR zeichnet jedenfalls weder in dieser Bestimmung noch in der allgemeinen Systematik einen Vorrang der Leistungsklage vor der identischen negativen Feststellungsklage vor. Dass die zutreffende Auslegung von <ref-law> mit der Praxis des EuGH zur Rechtshängigkeit nach Art. 21 des Brüsseler Übereinkommens vom 27. September 1968 über die gerichtliche Zuständigkeit und die Vollstreckung gerichtlicher Entscheidungen in Zivil- und Handelssachen (EuGVÜ; vgl. nunmehr Art. 27 EuGVVO; Urteile des EuGH vom 6. Dezember 1994 C-406/92 Tatry/Maciej Rataj, Slg. 1994 I-5460; vom 8. Dezember 1987 144/86 Gubisch Maschinenfabrik/Palumbo, Slg. 1987 S. 4871) und des schweizerischen Bundesgerichts zur entsprechenden Regelung des Lugano-Übereinkommens (LugÜ, SR 0.275.12; vgl. <ref-ruling> E. 6; <ref-ruling> E. 4b S. 349; <ref-ruling> E. 5) übereinstimmt, steht der richtigen Auslegung nicht entgegen, sondern kann als zusätzliche Bestätigung deren Richtigkeit angeführt werden.
3.5 <ref-law> behält schliesslich für die Einrede der Rechtshängigkeit vor, dass die Entscheidung des Gerichts, bei dem die erste Klage anhängig gemacht worden ist, in dem Staat nicht vollstreckt werden kann, in dem die neue Klage erhoben wird. Die Vollstreckung von Urteilen, mit denen festgestellt wird, dass eine Partei eine bestimmte Leistung nicht schuldet, erfolgt in gleicher Weise wie diejenige von Entscheidungen, mit denen eine Leistungsklage abgewiesen wird. Der Beklagte kann ihre Rechtskraft einredeweise geltend machen (vgl. HERBER/PIPER, a.a.O., N. 25 zu <ref-law> mit Verweisen; DEMUTH, a.a.O., N. 59 zu <ref-law>; KOLLER, a.a.O., N. 8 zu <ref-law>; STAUB/HELM, Grosskommentar zum Handelsgesetzbuch, 4. Aufl., Berlin/New York 2002, N. 51 zu <ref-law>). In welcher Form die "Vollstreckung" erfolgt, regelt Art. 31 Abs. 2 in fine CMR nicht (vgl. auch das Urteil des englischen Court of Appeal vom 23. Januar 2001, [2001] EWCA Civ 61 Rz. 94, wonach "enforceable" im Kontext von <ref-law> im Sinne von "capable of being given effect" zu verstehen ist). Es ist nun jedoch nicht ersichtlich und die Beschwerdeführerin weist nicht nach, dass im vorliegenden Fall Anhaltspunkte dafür bestehen könnten, dass das Urteil der niederländischen Gerichte in der Schweiz nicht anerkannt und damit - je nach Ausgang des Verfahrens - in der Form durchgesetzt werden könnte, wie dies für entsprechende schweizerische Feststellungsurteile vorgesehen ist.
3.6 Die Vorinstanz hat <ref-law> zutreffend ausgelegt mit dem Schluss, dass die Einrede der Rechtshängigkeit begründet ist und daher die Gerichte in der Schweiz unzuständig sind.
4. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Die Beschwerdeführerin wird bei diesem Ausgang des Verfahrens kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 10'000.-- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 12'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Kantonsgericht Basel-Landschaft, Abteilung Zivilrecht, schriftlich mitgeteilt.
Lausanne, 25. September 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann