Sachverhalt:
A. X._ ist bei der A._ Krankenversicherung AG nach KVG (SR 832.10) und VVG (SR 221.229.1) versichert. Am 2. Februar 2011 erstattete sie bei der Staatsanwaltschaft des Kantons Basel-Stadt Strafanzeige gegen die A._ Krankenversicherung AG wegen des Verdachts auf Betrug i.S.v. <ref-law>. Sie wirft der A._ Krankenversicherung AG vor, den Versicherten - so auch ihr selbst - vor und bis zum Vertragsabschluss zu verschweigen, dass sie in der Zusatzversicherung "B._" einen Selbstbehalt von Fr. 600.-- pro Jahr zu tragen haben. Weder auf der Internetseite der A._ Krankenversicherung AG noch in der Offerte fände sich ein entsprechender Hinweis. Lediglich in den Allgemeinen Versicherungsbedingungen (AVB) und in der Versicherungspolice, die die Kundin bzw. der Kunde nach dem Vertragsabschluss erhalte, werde der Selbstbehalt erwähnt. Es bestehe damit zumindest ein Anfangsverdacht, dass die A._ Krankenversicherung AG den Straftatbestand des Betrugs erfülle.
In der Folge wurde im Rahmen eines polizeilichen Vorermittlungsverfahrens eine Stellungnahme der A._ Krankenversicherung AG eingeholt. Am 11. April 2011 verfügte die Staatsanwaltschaft die Nichtanhandnahme der Angelegenheit mit der Begründung, das angezeigte Verhalten erfülle den Tatbestand des Betrugs eindeutig nicht.
Diese Verfügung focht X._ am 26. April 2011 beim Appellationsgericht des Kantons Basel-Stadt an. Mit Entscheid vom 5. Juli 2012 wies der Appellationsgerichtspräsident die Beschwerde ab.
B. Mit Beschwerde in Strafsachen vom 24. August 2012 beantragt X._, der Entscheid des Appellationsgerichtspräsidenten vom 5. Juli 2012 und die Nichtanhandnahmeverfügung der Staatsanwaltschaft vom 11. April 2011 seien aufzuheben, und die Staatsanwaltschaft sei anzuweisen, eine Strafuntersuchung zu eröffnen. Eventualiter sei die Sache zur neuen Beurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen.
Die Staatsanwaltschaft und der Appellationsgerichtspräsident stellen Antrag auf Beschwerdeabweisung. Die Beschwerdegegnerin beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei diese abzuweisen. In ihrer abschliessenden Stellungnahme vom 31. Oktober 2012 hält die Beschwerdeführerin an ihrem Standpunkt fest.

Erwägungen:
1. Der angefochtene Entscheid bestätigt, dass das von der Beschwerdeführerin angestrebte Strafverfahren nicht an die Hand genommen wird. Es handelt sich um einen Endentscheid einer letzten kantonalen Instanz in einer Strafsache, gegen den die Beschwerde in Strafsachen zulässig ist (Art. 78 Abs. 1, Art. 80 Abs. 1, Art. 90 BGG).
Zur Beschwerde in Strafsachen ist nach <ref-law> berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a) und ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat (lit. b). Nach Art. 81 Abs. 1 lit. b Ziff. 5 BGG wird der Privatklägerschaft ein rechtlich geschütztes Interesse zuerkannt, wenn der angefochtene Entscheid sich auf die Beurteilung ihrer Zivilansprüche auswirken kann. Dies verlangt grundsätzlich von der Privatklägerin, dass sie bereits adhäsionsweise Zivilforderungen geltend gemacht hat. Ausnahmsweise, bei Nichtanhandnahme oder Einstellung des Strafverfahrens, ist auf dieses Erfordernis zu verzichten. Immerhin ist jedoch erforderlich, dass im Verfahren vor Bundesgericht dargelegt wird, aus welchen Gründen sich der angefochtene Entscheid inwiefern auf welche Zivilforderungen auswirken kann (<ref-ruling> E. 1.3.1 S. 247).
Die Beschwerdeführerin hat am vorinstanzlichen Verfahren teilgenommen. Sie hat Strafanzeige wegen Betrugs gestellt und den Zusammenhang zwischen dem angefochtenen Entscheid und ihren Zivilforderungen aufgezeigt, indem sie einen Schaden von Fr. 675.-- behauptet. Dies ist für die Bejahung der Legitimation nach Art. 81 Abs. 1 lit. b Ziff. 5 BGG hinreichend. Auf die Beschwerde ist deshalb grundsätzlich einzutreten.
2. 2.1 Die Beschwerdeführerin bringt vor, die Staatsanwaltschaft habe fälschlicherweise die Strafuntersuchung nicht an die Hand genommen (<ref-law>), statt - wenn schon - die Einstellung des Strafverfahrens zu verfügen (<ref-law>). Die Vorinstanz, welche diesen Entscheid geschützt habe, habe insoweit ein falsches Beweismass angewendet, da sie nicht geprüft habe, ob der Straftatbestand des Betrugs (<ref-law>) eindeutig nicht erfüllt sei.
2.2 Gemäss <ref-law> verfügt die Staatsanwaltschaft die Nichtanhandnahme, sobald aufgrund der Strafanzeige oder des Polizeirapports feststeht, dass die fraglichen Straftatbestände oder die Prozessvoraussetzungen eindeutig nicht erfüllt sind.
Bei der Frage, ob ein Strafverfahren durch die Strafverfolgungsbehörde über eine Nichtanhandnahme erledigt werden kann, gilt im schweizerischen Strafprozessrecht der Grundsatz "in dubio pro duriore". Dieser Grundsatz fliesst aus dem Legalitätsprinzip (<ref-law> und <ref-law> i.V.m. Art. 319 Abs. 1 und Art. 324 Abs. 1 StPO; <ref-ruling> E. 4.2 S. 91) und bedeutet, dass eine Nichtanhandnahme durch die Staatsanwaltschaft gestützt auf <ref-law> grundsätzlich nur bei klarer Straflosigkeit bzw. offensichtlich fehlenden Prozessvoraussetzungen angeordnet werden darf. Klare Straflosigkeit liegt vor, wenn es sicher ist, dass der Sachverhalt unter keinen Straftatbestand fällt, was namentlich bei rein zivilrechtlichen Streitigkeiten der Fall ist. Bei der Beurteilung dieser Frage verfügen die Staatsanwaltschaft und die Vorinstanz über einen gewissen Spielraum, den das Bundesgericht mit Zurückhaltung überprüft (<ref-ruling> E. 4.1.2 S. 91). Im Zweifelsfall - wenn die Sach- und/oder die Rechtslage nicht von vornherein klar sind - ist eine Untersuchung zu eröffnen (vgl. <ref-ruling> E. 7 S. 226 f., 285 E. 2.3 S. 287 f.).
Bei der Frage, ob ein Strafverfahren durch die Strafverfolgungsbehörde über eine Nichtanhandnahme erledigt werden kann, gilt im schweizerischen Strafprozessrecht der Grundsatz "in dubio pro duriore". Dieser Grundsatz fliesst aus dem Legalitätsprinzip (<ref-law> und <ref-law> i.V.m. Art. 319 Abs. 1 und Art. 324 Abs. 1 StPO; <ref-ruling> E. 4.2 S. 91) und bedeutet, dass eine Nichtanhandnahme durch die Staatsanwaltschaft gestützt auf <ref-law> grundsätzlich nur bei klarer Straflosigkeit bzw. offensichtlich fehlenden Prozessvoraussetzungen angeordnet werden darf. Klare Straflosigkeit liegt vor, wenn es sicher ist, dass der Sachverhalt unter keinen Straftatbestand fällt, was namentlich bei rein zivilrechtlichen Streitigkeiten der Fall ist. Bei der Beurteilung dieser Frage verfügen die Staatsanwaltschaft und die Vorinstanz über einen gewissen Spielraum, den das Bundesgericht mit Zurückhaltung überprüft (<ref-ruling> E. 4.1.2 S. 91). Im Zweifelsfall - wenn die Sach- und/oder die Rechtslage nicht von vornherein klar sind - ist eine Untersuchung zu eröffnen (vgl. <ref-ruling> E. 7 S. 226 f., 285 E. 2.3 S. 287 f.).
2.3 2.3.1 Die Beschwerdeführerin erstattete, wie dargelegt (vgl. Sachverhalt lit. A.), am 2. Februar 2011 bei der Staatsanwaltschaft Strafanzeige gegen die A._ Krankenversicherung AG wegen des Verdachts auf Betrug. Im Rahmen eines polizeilichen Vorermittlungsverfahrens wurde in der Folge eine Stellungnahme der A._ Krankenversicherung AG eingeholt. Eine Strafuntersuchung wurde von der Staatsanwaltschaft hingegen nicht eröffnet (vgl. insoweit <ref-law>). Vielmehr verfügte die Staatsanwaltschaft am 11. April 2011 gestützt auf den Polizeirapport direkt die Nichtanhandnahme (vgl. <ref-law>).
Dieses Vorgehen ist bundesrechtskonform. Ein Strafverfahren kann, wie vorliegend geschehen, ohne eigene Untersuchung der Staatsanwaltschaft beendet werden, so wenn die Staatsanwaltschaft ein Verfahren allein gestützt auf die polizeilichen Ermittlungsergebnisse durch eine Nichtanhandnahmeverfügung abschliesst (Urteile 1B_67/2012 vom 29. Mai 2012 E. 2 und 1B_271/2012 vom 6. September 2012 E. 2; Niklaus Schmid, StPO Praxiskommentar, 2009, N. 2 zu <ref-law>; Nathan Landshut, in: Donatsch/Hansjakob/Lieber [Hrsg.], Kommentar zur StPO, 2010, N. 7 zu <ref-law>; Christof Riedo/Anastasia Falkner, in: Basler Kommentar StPO, N. 8 und N. 21 zu <ref-law>; Beat Rhyner, in: Basler Kommentar StPO, N. 2 zu <ref-law>).
2.3.2 Die Vorinstanz hat in ihrer Entscheidbegründung ausdrücklich erwogen, eine Nichtanhandnahme gemäss <ref-law> dürfe nur dann erfolgen, wenn der Straftatbestand eindeutig nicht erfüllt sei und die Führung eines Strafverfahrens deshalb als geradezu aussichtslos erscheine (angefochtener Entscheid E. 3.1). Im Ergebnis ist die Vorinstanz alsdann zum Schluss gekommen, es sei nicht zu beanstanden, dass die Staatsanwaltschaft angenommen habe, das Tatbestandsmerkmal der arglistigen Täuschung sei vorliegend offensichtlich nicht erfüllt (angefochtener Entscheid E. 3.2.2).
Die Vorinstanz hat damit die Voraussetzungen von <ref-law> korrekt wiedergegeben und geprüft. Die Rüge der Beschwerdeführerin, die Vorinstanz habe ein falsches Beweismass angewendet, erweist sich als unbegründet.
3. 3.1 Die Beschwerdeführerin lastet der Vorinstanz eine qualifiziert unrichtige Sachverhaltsfeststellung an.
3.2 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Soweit die vorinstanzlichen Sachverhaltsfeststellungen beanstandet werden und diese für den Ausgang des Verfahrens entscheidend sind, kann nur geltend gemacht werden, die Feststellungen seien offensichtlich unrichtig oder beruhten auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Offensichtlich unrichtig bedeutet willkürlich (<ref-ruling> E. 2.4 S. 314 mit Hinweis).
Willkür im Sinne von <ref-law> liegt nach ständiger Rechtsprechung nicht schon vor, wenn das angefochtene Urteil nicht mit der Darstellung der Beschwerdeführerin übereinstimmt oder eine andere Lösung oder Würdigung vertretbar erscheint oder gar vorzuziehen wäre, sondern nur, wenn der angefochtene Entscheid auf einer schlechterdings unhaltbaren oder widersprüchlichen Beweiswürdigung beruht, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.4 S. 5).
3.3 Die Vorinstanz hat in tatsächlicher Hinsicht namentlich festgestellt, in den AVB werde bei der Zusatzversicherung "B._" explizit auf den Selbstbehalt von Fr. 600.-- hingewiesen (Art. 23). Mit ihrer Unterzeichnung des Versicherungsantrags habe die Beschwerdeführerin ausdrücklich bestätigt, die AVB und die Zusatzbedingungen erhalten zu haben und deren Inhalt rechtsverbindlich anzuerkennen. Es sei daher davon auszugehen, dass die Beschwerdeführerin spätestens bei Eingang der Offerte der Beschwerdegegnerin vom Inhalt der AVB Kenntnis gehabt habe oder zumindest hätte haben können. Die AVB seien entgegen der Behauptung der Beschwerdeführerin keineswegs unübersichtlich und unklar. Vielmehr fänden sich die Angaben zum Selbstbehalt genau an jener Stelle, wo sie zu erwarten seien, nämlich unter den ergänzenden Bestimmungen zur Zusatzversicherung "B._". Der Hinweis auf den Selbstbehalt sei unmissverständlich formuliert und durch ein Ausrufezeichen hervorgehoben.
3.4 Diese tatsächlichen Feststellungen werden von der Beschwerdeführerin nicht substanziiert bestritten. Vielmehr stellt sie mit ihren Ausführungen der vorinstanzlichen Begründung lediglich ihre eigene Sicht der Dinge gegenüber, ohne darzulegen, inwiefern die Feststellungen der Vorinstanz zu den AVB unhaltbar sein sollten.
Im Weiteren zeigt die Beschwerdeführerin nicht auf und es ist auch nicht ersichtlich, dass die übrigen von ihr als unzutreffend gerügten Sachverhaltsfeststellungen der Vorinstanz ([mangelnde] Hinweise auf den Selbstbehalt auf der Internetseite und in der Offerte sowie in den Beratungsgesprächen und im Versicherungsantrag; Wissen des Durchschnittskonsumenten) für den Ausgang des Verfahrens entscheidend gewesen wären.
3.5 Zu prüfen bleibt, ob die Vorinstanz zu Recht geschlossen hat, der Tatbestand des Betrugs gemäss <ref-law> sei mangels arglistiger Täuschung offensichtlich nicht erfüllt.
Nach <ref-law> macht sich des Betrugs namentlich schuldig, wer in der Absicht, sich oder einen anderen unrechtmässig zu bereichern, jemanden durch Vorspiegelung oder Unterdrückung von Tatsachen arglistig irreführt und so den Irrenden zu einem Verhalten bestimmt, wodurch dieser sich selbst oder einen anderen am Vermögen schädigt.
Die Erfüllung des Tatbestands erfordert mithin eine arglistige Täuschung. Betrügerisches Verhalten ist strafrechtlich erst relevant, wenn der Täter mit einer gewissen Raffinesse oder Durchtriebenheit täuscht. Einerseits muss sich aus der Art und Intensität der angewendeten Täuschungsmittel eine erhöhte Gefährlichkeit ergeben (betrügerische Machenschaften, Lügengebäude). Einfache Lügen, plumpe Tricks oder leicht überprüfbare falsche Angaben genügen demnach nicht. Andererseits erfolgt die Eingrenzung des Betrugstatbestands über die Berücksichtigung der Eigenverantwortlichkeit des Opfers. Danach ist ausgehend vom Charakter des Betrugs als Beziehungsdelikt, bei welchem der Täter auf die Vorstellung des Opfers einwirkt und dieses veranlasst, sich selbst durch die Vornahme einer Vermögensverfügung zugunsten des Täters oder eines Dritten zu schädigen, zu prüfen, ob das Opfer den Irrtum bei Inanspruchnahme der ihm zur Verfügung stehenden Selbstschutzmöglichkeiten hätte vermeiden können. Wer sich mit einem Mindestmass an Aufmerksamkeit selbst hätte schützen bzw. den Irrtum durch ein Minimum zumutbarer Vorsicht hätte vermeiden können, wird strafrechtlich nicht geschützt. Dabei ist die jeweilige Lage und Schutzbedürftigkeit des Betroffenen im Einzelfall entscheidend.
Arglist wird nach all dem - soweit das Opfer sich nicht in leichtfertiger Weise seiner Selbstschutzmöglichkeiten begibt - in ständiger Rechtsprechung bejaht, wenn der Täter ein ganzes Lügengebäude errichtet oder sich besonderer Machenschaften oder Kniffe bedient. Ein Lügengebäude und damit Arglist ist nicht schon gegeben, wenn verschiedene Lügen bloss aneinandergereiht werden, sondern erst wenn die Lügen von besonderer Hinterhältigkeit zeugen und derart raffiniert aufeinander abgestimmt sind, dass sich auch das kritische Opfer täuschen lässt. Ist das nicht der Fall, scheidet Arglist jedenfalls dann aus, wenn sowohl das vom Täter gezeichnete Bild als Ganzes wie auch die falschen Angaben für sich allein in zumutbarer Weise überprüfbar gewesen wären und schon die Aufdeckung einer einzigen Lüge zur Aufdeckung des ganzen Schwindels geführt hätte. Arglist ist aber auch bei einfachen falschen Angaben gegeben, wenn deren Überprüfung nicht oder nur mit besonderer Mühe möglich oder nicht zumutbar ist, oder wenn der Täter den Getäuschten von der möglichen Überprüfung abhält oder nach den Umständen voraussieht, dass dieser die Überprüfung der Angaben auf Grund eines besonderen Vertrauensverhältnisses unterlassen werde (vgl. zum Ganzen <ref-ruling> E. 5.2 S. 79 ff. mit Hinweisen).
3.6 Wie die Vorinstanz, ohne in Willkür zu verfallen, festgestellt hat, sind die der Beschwerdeführerin vor dem Vertragsabschluss zugestellten AVB übersichtlich gestaltet. Der Hinweis auf den Selbstbehalt findet sich unter den ergänzenden Bestimmungen zur Zusatzversicherung "B._", ist mit einem Ausrufezeichen hervorgehoben und unmissverständlich formuliert. Die Beschwerdeführerin hat im Versicherungsantrag unterschriftlich bestätigt, die AVB zu kennen und diese als rechtsverbindlich anzuerkennen. Gestützt auf diesen willkürfrei erstellten Sachverhalt (vgl. auch E. 3.3 hiervor) hat die Vorinstanz auf der Grundlage der dargestellten bundesgerichtlichen Rechtsprechung (E. 3.5 hiervor) zu Recht gefolgert, das Tatbestandsmerkmal der arglistigen Täuschung sei eindeutig nicht erfüllt. Wie die Vorinstanz im angefochtenen Entscheid zutreffend ausgeführt hat, kann nicht jede unterlassene explizite Aufklärung über allfällige Nachteile eines Vertrags als betrugsrelevante arglistige Täuschung betrachtet werden. Im zu beurteilenden Fall war es der Beschwerdeführerin möglich und auch zumutbar, die AVB zur Zusatzversicherung "B._" zu prüfen. Insbesondere hat die Beschwerdegegnerin die Beschwerdeführerin nicht von der Überprüfung der AVB abgehalten, und es kann auch nicht gesagt werden, dass zwischen potenziellen Versicherungsnehmern und Krankenkassen generell ein besonderes Vertrauensverhältnis bestehen würde.
4. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang trägt die Beschwerdeführerin die Gerichtskosten (<ref-law>). Sie hat der obsiegenden, anwaltlich vertretenen Beschwerdegegnerin eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, sowie der Staatsanwaltschaft und dem Appellationsgericht des Kantons Basel-Stadt, Appellationsgerichtspräsident, schriftlich mitgeteilt.
Lausanne, 26. November 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Stohner