Sachverhalt: A. A.a. Die X._ AG ist eine Aktiengesellschaft mit Sitz in A._. Sie bezweckt insbesondere die Beratung von Personen, Unternehmen und Institutionen des privaten und öffentlichen Rechts in Fragen des Schulden- und Forderungsmanagements, die Entwicklung von Strategien, Methoden und Konzepten für die Bewirtschaftung von Forderungen und Schulden sowie die Erbringung von Beratungsdienstleistungen zur Verbesserung und Erleichterung der Schuldenbewirtschaftung und bei der Erfüllung von internationalen Schulden- und Schuldendienstverpflichtungen. A.b. Die Tschechische Republik, handelnd durch ihr Finanzministerium, schloss am 22. März 2001 mit der X._ AG ein "Option Agreement" betreffend eine Forderung der Tschechischen Republik gegen die ehemalige Bundesrepublik Jugoslawien. Über einen Teil dieser Forderung hatte die Tschechische Republik bereits verfügt; im " Option Agreement " verpflichtete sie sich für den Fall, dass sie inskünftig die Tilgung der Restforderung in Betracht ziehe, vorab der X._ AG den Kauf der Forderung anzubieten. Diese verpflichtete sich im Gegenzug, gegenüber dem Finanzministerium innerhalb von 60 Kalendertagen nach Eingang des Angebots schriftlich dazu Stellung zu nehmen, widrigenfalls das Finanzministerium berechtigt wäre, über die Forderung anderweitig zu verfügen. A.c. Mit Schreiben vom 18. Juli 2003 teilte das Finanzministerium der Tschechischen Republik der X._ AG mit, die Tschechische Republik beabsichtige, einen Vertrag mit einem Dritten abzuschliessen, um ihre Staatsforderung gegen die ehemalige Bundesrepublik Jugoslawien (nunmehr gegen die Republik Serbien und Montenegro) zu regulieren. Es sei ein Angebot für eine Regulierung dieser Forderungen in der Höhe von 13 % derselben eingegangen. Das Finanzministerium ersuchte die X._ AG um Mitteilung " mit einem beglaubigten Schreiben ", spätestens bis zum 31. Juli 2003 eintreffend, ob sie den noch verbleibenden Forderungsteil zu vergleichbaren Bedingungen kaufen oder aber das Finanzministerium der Tschechischen Republik von seinen Pflichten aus dem "Option Agreement" ohne Haftung befreien möchte. Mit Faxschreiben an den Generaldirektor des Tschechischen Finanzministeriums vom 28. Juli 2003 teilte die X._ AG mit, dass sie am Kauf von 75 % der Schuld interessiert sei, und ersuchte um Terminvorschläge für ein Treffen, um das Geschäft abzuwickeln. A.d. In der Folge stellte sich die X._ AG auf den Standpunkt, es sei gestützt auf diesen Vorgang ein Vertrag zur Abtretung der Forderung zustande gekommen, woraus die Tschechische Republik verpflichtet sei, ihr eine entsprechende Abtretungsurkunde zu übersenden. Die Tschechische Republik bestritt das Zustandekommen eines solchen Vertrags. B. B.a. Mit Klage vom 21. Dezember 2007 an das Kantonsgericht von Appenzell Ausserrhoden beantragte die X._ AG (Klägerin) im Hauptbegehren, die Tschechische Republik (Beklagte) sei zu verurteilen, ihr mindestens USD 13'171'649.30 (entsprechend 13'171'649.30 Clearing-Koruna, "XCS") bzw. den entsprechenden Betrag in Landeswährung zu bezahlen, sowie mindestens 45 % von 75 % sämtlicher auf der gesamten Forderung der Beklagten gegen die ehemalige Bundesrepublik Jugoslawien in der Höhe von USD 54'881'926.28 (entsprechend XCS 54'881'926.28) aufgelaufenen und aufgerechneten Zinsen bzw. den entsprechenden Betrag in Landeswährung, abzüglich des durchschnittlichen Anlagebetrages des Betrages von USD 5'351'000.81 (entsprechend XCS 5'351'000.81) seit 28. Juli 2003, zuzüglich Zins zu 5 % seit 31. Mai 2007. Das Kantonsgericht von Appenzell Ausserrhoden bejahte seine örtliche und sachliche Zuständigkeit und die Anwendbarkeit von tschechischem Recht in der Sache. Es ordnete die Durchführung eines Beweisverfahrens an und holte beim Schweizerischen Institut für Rechtsvergleichung eine Offerte für die Erstellung eines Rechtsgutachtens zur Klärung aller entscheidrelevanten Fragen zum Tschechischen Recht ein. Wegen der voraussichtlich hohen Kosten und langen Dauer der Begutachtung sah die Verfahrensleitung indes davon ab und schlug den Parteien stattdessen die Anwendung schweizerischen Rechts als Ersatzrecht vor. Die Klägerin erklärte sich damit einverstanden, während die Beklagte die Anwendung schweizerischen Rechts als Ersatzrecht ablehnte und den Erlass eines Vorentscheids über die von ihr bestrittene örtliche und sachliche Zuständigkeit des Kantonsgerichts beantragte. Mit Zwischenentscheid vom 25. Januar 2011 bejahte das Kantonsgericht Appenzell Ausserrhoden seine örtliche und sachliche Zuständigkeit. B.b. Mit Eingabe vom 11. Februar 2011 focht die Beklagte (Appellantin) den Zwischenentscheid des Kantonsgerichts beim Obergericht von Appenzell Ausserrhoden mit Berufung nach Massgabe der schweizerischen Zivilprozessordnung (ZPO) an. Sie beantragte die Aufhebung des kantonsgerichtlichen Zwischenentscheids sowie Nichteintreten auf die Klage. Die Klägerin (Appellatin) beantragte Abweisung des Rechtsmittels sowie die Feststellung, dass das Kantonsgericht für die Beurteilung der Streitsache zuständig sei. Das Obergericht behandelte das Rechtsmittel als Appellation nach Massgabe der bis 31. Dezember 2011 in Kraft stehenden Zivilprozessordnung des Kantons Appenzell Ausserrhoden vom 27. April 1980 (ZPO/AR). Mit Urteil vom 21. Mai 2012, versandt am 16. Oktober 2012, hiess das Obergericht die Appellation gut, hob den angefochtenen Entscheid auf und stellte fest, dass die Gerichte des Kantons Appenzell Ausserrhoden zur Beurteilung der Streitsache nicht zuständig seien. C. Mit Eingabe vom 16. November 2012 führt die X._ AG (Beschwerdeführerin) gegen das Urteil des Obergerichts von Appenzell Ausserrhoden von 21. Mai 2012 Beschwerde in Zivilsachen an das Bundesgericht mit dem Antrag, den angefochtenen Entscheid aufzuheben, die Unzuständigkeitseinrede abzuweisen und festzustellen, dass die Gerichte des Kantons Appenzell Ausserrhoden zur Beurteilung der Forderung der Beschwerdeführerin zuständig seien; eventualiter sei das Verfahren an die Vorinstanz zur Entscheidung, insbesondere zur Durchführung eines Beweisverfahrens, zurückzuweisen. Mit Beschwerdeantwort vom 31. Januar 2013 beantragt die Tschechische Republik (Beschwerdegegnerin) Abweisung der Beschwerde, soweit Eintreten. Die Vorinstanz verzichtete auf Stellungnahme. Die Parteien reichten Replik und Duplik ein. D. Mit Präsidialverfügung vom 17. Dezember 2012 wurde das Gesuch um Erteilung der aufschiebenden Wirkung abgewiesen. 