Sachverhalt:
A. X._ hätte die Schweiz nach dem rechtskräftigen Entscheid des Bundesamtes für Flüchtlinge per 25. Juli 2002 verlassen müssen. Dies tat sie nicht. Am 27. Januar 2011 wurde sie wegen rechtswidrigen Aufenthaltes verurteilt.
Die Anklage wirft der Angeschuldigten vor, sich zwischen dem 23. Dezember 2010 und dem 5. Oktober 2011 weiterhin widerrechtlich in der Schweiz aufgehalten zu haben.
B. Das Bezirksgericht Brugg verurteilte die Angeschuldigte wegen rechtswidrigen Aufenthaltes zu einer unbedingten Freiheitsstrafe von drei Monaten und widerrief die bedingte Geldstrafe von 180 Tagessätzen zu Fr. 30.-- vom 27. Januar 2011.
Das Obergericht des Kantons Aargau hiess die Berufung der Angeschuldigten am 21. August 2012 gut und stellte das Strafverfahren gegen sie ein.
C. Die Staatsanwaltschaft Brugg-Zurzach erhebt Beschwerde in Strafsachen. Sie beantragt, den angefochtenen Entscheid aufzuheben und die Angeschuldigte entsprechend dem Urteil des Bezirksgerichts Brugg zu verurteilen. Eventualiter sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
D. Das Obergericht des Kantons Aargau verzichtet auf eine Stellungnahme. X._ beantragt, die Beschwerde sei abzuweisen.

Erwägungen:
1. 1.1 Die Beschwerdeführerin rügt, die Vorinstanz habe zu Unrecht angenommen, das Rückführungsverfahren habe gegenüber einer Bestrafung wegen illegalen Aufenthalts Vorrang. Aufgrund des Schengen-Besitzstandes sei die Schweiz verpflichtet, die Richtlinie 2008/115/EG des Europäischen Parlaments und des Rates vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger (ABl. L 348 vom 24. Dezember 2008, S. 98 ff.; nachfolgend: EU-Rückführungsrichtlinie) zu beachten. Die Schweiz habe sie gemäss der Beschwerdeführerin in Landesrecht umgesetzt, sich jedoch der Rechtsprechung des Europäischen Gerichtshofs (EuGH) nicht unterworfen. Die EU-Rückführungsrichtlinie sehe vor, dass bei der Wegweisung von illegal anwesenden Personen Zwangsmassnahmen angewendet werden dürften, jedoch nicht müssten. Eine Verpflichtung bestehe insbesondere nicht, wenn sich sämtliche Bemühungen des betreffenden Staates als aussichtslos erwiesen, weil die Person nicht kooperiere. Zudem habe der EuGH lediglich entschieden, dass eine wegen illegalen Aufenthalts ausgesprochene Strafe die Rückführung nicht verzögern und damit die praktische Wirksamkeit der EU-Rückführungsrichtlinie nicht beeinträchtigen dürfe.
Die Beschwerdeführerin bringt vor, nach einem längerem illegalen Aufenthalt könne eine Freiheitsstrafe die Wegweisung nicht mehr beeinträchtigen, da eine freiwillige Ausreise nicht stattfinde und eine sofortige Abschiebung nicht zu erwarten sei. Treffe dieser unwahrscheinliche Fall dennoch ein, könne vom Opportunitätsprinzip gemäss Art. 115 Abs. 4 des Bundesgesetzes über die Ausländerinnen und Ausländer (AuG; SR 142.20) Gebrauch gemacht werden. Es sei realitätsfremd, wenn die Vorinstanz verlange, die Beschwerdegegnerin zuerst in Ausschaffungshaft zu versetzen, bevor ihre Straftaten strafrechtlich geahndet werden könnten. Weder Art. 115 Abs. 4 AuG noch <ref-law> böten eine Grundlage, das Verfahren einzustellen (Beschwerde, S. 3 ff.).
Die Beschwerdeführerin begründet in ihren weiteren Ausführungen, weshalb die erste Instanz zu Recht eine unbedingte Freiheitsstrafe von drei Monaten ausgefällt und die bedingte Vorstrafe widerrufen hat (Beschwerde, S. 8 ff.).
1.2 Die Vorinstanz erwägt, die EU-Rückführungsrichtlinie habe zum Ziel, in den Mitgliedstaaten das Rückführungsverfahren bei illegal anwesenden Personen aus Drittstaaten zu vereinheitlichen. Aufgrund des Schengen-Besitzstandes sei die EU-Rückführungsrichtlinie für die Schweiz verbindlich. Das nationale Recht sei richtlinienkonform auszulegen, weshalb auch die EuGH-Rechtsprechung zu berücksichtigen sei. Nationale Vorschriften - auch strafrechtliche Bestimmungen - dürften die Verwirklichung der EU-Rückführungsrichtlinie nicht gefährden. Die Schweiz sei daher nicht befugt, eine Freiheitsstrafe allein deshalb zu verhängen, weil sich ein Drittstaatsangehöriger nach Ablauf der Ausreisefrist hier illegal aufhalte. Vielmehr hätte sie die Anstrengungen zur Vollstreckung der Rückkehrentscheidung weiterzuführen. Verlangt werde, dass alles für den Vollzug der Rückkehrentscheidung Zumutbare vorgekehrt worden sei, die Rückkehr jedoch am Verhalten des Betroffenen scheitere. Eine innerstaatliche Sanktionierung sei erst möglich, wenn die höchstzulässige Dauer der Ausschaffungshaft erreicht und sich die betreffende Person trotz Zwangsmassnahmen weiterhin illegal in der Schweiz aufhalte (Urteil, S. 6 ff.).
Das Amt für Migration und Integration des Kantons Aargau (nachfolgend: MIKA) habe im Anklagezeitraum nicht alle zumutbaren Schritte unternommen, um die Wegweisungsverfügung vom 24. Juli 2002 zu vollziehen. Es habe das Bundesamt für Migration am 7. Februar 2011 gebeten, bei der mongolischen Vertretung einen Antrag um Ausstellung eines Ersatzreisedokumentes zu erstellen. Dieser Antrag sei wenige Tage später deponiert worden. Das MIKA habe nach einem Jahr mittels Eingrenzungsverfügung den zulässigen Aufenthaltsbereich der Beschwerdegegnerin auf den Kanton Aargau beschränkt. Zudem habe es in der entsprechenden Verfügung ausgeführt, dass ihr Verhalten die Anordnung von Durchsetzungshaft rechtfertige, vorerst jedoch darauf verzichtet werde. Dem MIKA wäre es jedoch möglich gewesen, bereits im Anklagezeitraum Durchsetzungshaft anzuordnen oder eine Eingrenzungsverfügung zu erlassen (Urteil, S. 7 f.).
1.3 Das Bundesgericht hat sich mit der Anwendung der EU-Rückführungsrichtlinie und dem Verhältnis zur innerstaatlichen Sanktionierbarkeit während des Rückführungsverfahrens befasst. Auf diese grundlegenden Ausführungen kann verwiesen werden (vgl. Urteil 6B_196/2012 vom 24. Januar 2013 E. 2).
1.4 Gemäss schriftlicher Stellungnahme des Bundesamtes für Migration vom 8. Oktober 2012 (Beschwerdebeilage, pag. 31 f.) kann ein mongolischer Staatsbürger freiwillig in die Mongolei zurückkehren. Er muss bei der Botschaft in Genf vorsprechen und seine Staatsangehörigkeit glaubhaft machen. Eine Beschaffung von Ausreisepapieren durch die Migrationsbehörden sei zwar möglich. Die Abklärungen dauerten jedoch selbst bei vorhandenen Dokumenten mehrere Monate bis Jahre. Zwangsweise Rückführungen in die Mongolei seien noch nie durchgeführt worden. Durchsetzungshaft könne nur im Einzelfall zur freiwilligen Rückkehr motivieren.
1.5 Im vorliegenden Fall haben die zuständigen Aargauer Behörden dem Bundesamt für Migration die notwendigen Anträge zur Papierbeschaffung zugestellt. Das Verfahren ist jedoch seit mehr als zwei Jahren bei der mongolischen Botschaft hängig. Die erstinstanzliche Freiheitsstrafe von drei Monaten ist nicht geeignet, die Rückführung der Beschwerdegegnerin zu verzögern oder zu verhindern, da sie innert absehbarer Frist lediglich freiwillig zurückkehren kann. Eine behördlich angeordnete Ausschaffung dauert mehrere Jahre und wurde in der Praxis noch nie vollzogen. Entgegen der Vorinstanz haben die Migrationsbehörden die notwendigen Schritte zur Ausschaffung unternommen. Die Vorinstanz verletzt daher Bundesrecht, indem sie die Beschwerdegegnerin nicht wegen rechtswidrigen Aufenthalts verurteilt hat.
2. Die Beschwerde ist gutzuheissen. Das Urteil des Obergerichts des Kantons Aargau vom 21. August 2012 ist aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin unterliegt mit ihrem Antrag auf kostenfällige Abweisung der Beschwerde, weshalb sie grundsätzlich kostenpflichtig wird (<ref-law>). Sie stellt indes ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung, das gutzuheissen ist. Ihre Bedürftigkeit ist ausgewiesen, und ihr Standpunkt kann nicht als aussichtslos bezeichnet werden, da die Rechtslage bis anhin unklar war (<ref-law>). Dem Rechtsvertreter der Beschwerdegegnerin ist für das bundesgerichtliche Verfahren eine angemessene Entschädigung aus der Bundesgerichtskasse auszurichten. Der Beschwerdeführerin ist keine Parteientschädigung zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Das Urteil des Obergerichts des Kantons Aargau vom 21. August 2012 wird aufgehoben und die Sache zur neuen Beurteilung an die Vorinstanz zurückgewiesen.
2. Das Gesuch der Beschwerdegegnerin um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen. Für das bundesgerichtliche Verfahren wird ihr Maja Gehrig, Brugg, als unentgeltliche Anwältin beigegeben.
3. Es werden keine Gerichtskosten erhoben.
4. Der Vertreterin der Beschwerdegegnerin wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 1'500.-- ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, Strafgericht, 2. Kammer, schriftlich mitgeteilt.
Lausanne, 11. März 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Keller