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. 