Sachverhalt:
A. X._ wird vorgeworfen, sie sei am 17. August 2010 ohne Visum mit dem Flugzeug in die Schweiz eingereist und habe sich damit der rechtswidrigen Einreise schuldig gemacht. Ausserdem habe sie sich nach Ablauf der rechtskräftigen Ausreisefrist vom 7. Oktober 2010 bis 12. Oktober 2011 illegal in der Schweiz aufgehalten.
B. Das Bezirksgericht Brugg verurteilte X._ am 15. Dezember 2011 wegen rechtswidriger Einreise und rechtswidrigen Aufenthalts zu einer Freiheitsstrafe von drei Monaten.
Das Obergericht des Kantons Aargau hiess die Berufung der Angeschuldigten am 14. 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 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. Als äthiopische Staatsangehörige könne die Beschwerdegegnerin nicht zwangsweise rückgeschafft werden, da die äthiopische Botschaft nur für freiwillige Rückkehrer ein Einreisedokument ausstelle. Deshalb sei vorliegend keine Ausschaffungshaft angeordnet worden. Einer strafrechtlichen Verfolgung stehe daher nichts entgegen. Weder Art. 115 Abs. 4 AuG noch <ref-law> böten eine Grundlage, das Verfahren einzustellen (Beschwerde, S. 3 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 ihre Anstrengungen weiterführen sollen, die Rückkehr zu vollstrecken. Eine innerstaatliche Sanktionierung sei erst möglich, wenn alle zumutbaren Massnahmen ergriffen worden seien und sich die betreffende Person trotz Zwangsmassnahmen weiterhin illegal in der Schweiz aufhalte (Urteil, S. 6 ff.).
Die Wegweisungsverfügung der Beschwerdegegnerin des Bundesamtes für Migration sei am 5. Oktober 2010 rechtskräftig geworden. Am 7. Oktober 2010 habe sie die für die Beschaffung von Reisepapieren erforderlichen Antragsformulare (ausser dem sogenannten Basic Data Sheet) ausgefüllt. Anlässlich des Rückkehrberatungsgesprächs vom 18. Oktober 2010 habe sie mehrfach unmissverständlich signalisiert, nicht nach Hause zurückkehren zu wollen. In den Akten ergäben sich keine Hinweise, dass das Migrationsamt im relevanten Zeitraum weitere Anstrengungen unternommen hätte, den Wegweisungsentscheid gegen sie zu vollziehen. Es sei weder versucht worden, Ersatzreisepapiere zu beschaffen noch die zwangsweise Rückführung einzuleiten. Die Beschwerdegegnerin habe die notwendigen Formulare ausgefüllt. Ihr könne daher nicht mangelnde Mitwirkung oder Vereitelung der Wegweisungsverfügung vorgeworfen werden (Urteil, S. 8 ff.).
1.3 Die Strafrechtliche Abteilung des Bundesgerichts 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 4. Oktober 2012 (Beschwerdebeilage, pag. 38 f.) kann ein äthiopischer Staatsbürger freiwillig nach Äthiopien zurückkehren. Er muss dazu bei der Botschaft in Genf vorsprechen und seine Staatsangehörigkeit glaubhaft machen. Reisepapiere würden seit mehr als zwölf Jahren lediglich freiwilligen Rückkehrern ausgestellt. Durchsetzungshaft könne nur im Einzelfall zur freiwilligen Rückkehr motivieren. Eine zwangsweise Rückschaffung sei nach Äthiopien nicht möglich.
1.5 Im vorliegenden Fall haben die zuständigen Aargauer Behörden dem Bundesamt für Migration die notwendigen Anträge zur Papierbeschaffung zugestellt. Die Ausschaffung ist jedoch blockiert, da die Beschwerdegegnerin nicht freiwillig zurückkehrt und die äthiopische Botschaft deshalb keine Reisepapiere ausstellt. Die erstinstanzliche Freiheitsstrafe von drei Monaten ist nicht geeignet, die Rückführung der Beschwerdegegnerin zu verzögern oder zu verhindern, da diese lediglich freiwillig in ihre Heimat zurückkehren kann und eine behördlich angeordnete Ausschaffung entfällt. Entgegen der Vorinstanz haben die Migrationsbehörden die notwendigen Schritte zur Ausschaffung unternommen. Deren Vollzug scheiterte jedoch am fehlenden Ausreisewillen der Beschwerdegegnerin. Die Vorinstanz verletzt daher Bundesrecht, indem sie die Beschwerdegegnerin nicht wegen rechtswidriger Einreise und rechtswidrigen Aufenthalts verurteilt hat.
2. Die Beschwerde ist gutzuheissen. Das Urteil des Obergerichts des Kantons Aargau vom 14. 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 14. 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 Donato Del Duca, Aarau, als unentgeltlicher Anwalt beigegeben.
3. Es werden keine Gerichtskosten erhoben.
4. Dem Vertreter 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