Sachverhalt:
A. Das Bezirksamt Bremgarten erklärte X._ mit Strafbefehl vom 12. August 2010 der Veruntreuung, der Urkundenfälschung und des mehrfachen Diebstahls zum Nachteil seiner Arbeitgeberin, der Y._ AG, schuldig und verurteilte ihn zu einer bedingten Geldstrafe von 40 Tagessätzen zu Fr. 110.-- und einer Busse von Fr. 1'000.--.
Nach Einsprache erhob die Staatsanwaltschaft des Kantons Aargau am 24. September 2010 Anklage. Das Gerichtspräsidium Bremgarten sprach X._ mit Urteil vom 1. März 2011 vollumfänglich frei. Es eröffnete im Anschluss an die Verhandlung das Dispositiv mündlich und stellte es der Staatsanwaltschaft des Kantons Aargau gleichentags mit einer Kurzbegründung zu. Die Empfangsbestätigung der Oberstaatsanwaltschaft datiert vom 22. März 2011.
B. Die Oberstaatsanwaltschaft des Kantons Aargau stellte beim Gerichtspräsidium Bremgarten am 24. März 2011 ein "Motivierungsbegehren" und ersuchte "um Zustellung einer vollständig begründeten Ausfertigung des Urteils".
Das Gerichtspräsidium Bremgarten stellte den Parteien das begründete Urteil am 10. Mai 2011 zu. Die Oberstaatsanwaltschaft des Kantons Aargau meldete am 16. Mai 2011 beim Gerichtspräsidium Bremgarten die Berufung an und reichte am 24. Mai 2011 dem Obergericht des Kantons Aargau die Berufungserklärung ein. Die Privatklägerin, die Y._ AG, erhob am 27. Juni 2011 Anschlussberufung.
C. Das Obergericht des Kantons Aargau ordnete am 14. Februar 2012 die Durchführung des schriftlichen Berufungsverfahrens an. Nach abgeschlossenem Schriftenwechsel sprach es X._ von der Anklage des mehrfachen Diebstahls frei, erklärte ihn der Veruntreuung und der Urkundenfälschung schuldig und verurteilte ihn zu einer bedingten Geldstrafe von 30 Tagessätzen zu Fr. 110.-- sowie zu einer Busse von Fr. 600.--. Es schützte die Zivilforderung der Privatklägerin im Umfang von Fr. 2'700.--; im Übrigen wurde die Zivilklage auf den Zivilweg verwiesen.
D. X._ führt Beschwerde in Strafsachen. Er beantragt die Aufhebung des angefochtenen Urteils und die Feststellung, dass das Urteil des Gerichtspräsidiums Bremgarten vom 1. März 2011 in Rechtskraft erwachsen ist.
Das Obergericht des Kantons Aargau verzichtet auf eine Stellungnahme, die Oberstaatsanwaltschaft auf einen Antrag, und die Privatklägerin beantragt die Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Der Beschwerdeführer erachtet die Berufungsanmeldung durch die Oberstaatsanwaltschaft vom 16. Mai 2011 als verspätet und macht eine Verletzung von Art. 399 Abs. 1 der Schweizerischen Strafprozessordnung vom 5. Oktober 2007 (StPO; SR 312.0) geltend.
1.2 Die Vorinstanz stellt sich im angefochtenen Urteil auf den Standpunkt, dass die mit "Motivierungsbegehren" betitelte Eingabe der Staatsanwaltschaft vom 24. März 2011 inhaltlich einer Berufungsanmeldung im Sinne von <ref-law> entspricht (Urteil, S. 11).
1.3 Die Anklage vom 24. September 2010 erfolgte noch unter der Geltung des aargauischen Gesetzes vom 11. November 1958 über die Strafrechtspflege (Strafprozessordnung; aStPO/AG). Die Hauptverhandlung vor dem Gerichtspräsidium Bremgarten wurde am 1. März 2011 eröffnet. Nach den Übergangsbestimmungen der Strafprozessordnung (Art. 448 i.V.m. <ref-law>) ist somit für das Haupt- und das Rechtsmittelverfahren das neue Recht anwendbar.
1.4 Die Berufung ist dem erstinstanzlichen Gericht innert 10 Tagen seit Eröffnung des Urteils schriftlich oder mündlich zu Protokoll anzumelden (<ref-law>) und innert 20 Tagen seit der Zustellung des begründeten Urteils schriftlich zu erklären (<ref-law>). Massgebend für die Eröffnung des Urteils ist die Aushändigung oder Zustellung des Urteilsdispositivs im Anschluss an die Hauptverhandlung (<ref-law>).
1.5 Das Gerichtspräsidium Bremgarten eröffnete das Urteil mündlich und datierte das den Parteien schriftlich zugestellte Urteilsdispositiv auf den 1. März 2011. Die Staatsanwaltschaft erhielt zusätzlich eine mit dem gleichen Datum datierte Kurzbegründung, welche den übrigen Parteien offenbar vorenthalten wurde. Dispositiv und Kurzbegründung wurden am 14. März 2011 auch noch der Oberstaatsanwaltschaft zugestellt. Die Empfangsbestätigungen der Parteien und der Oberstaatsanwaltschaft für das Urteilsdispositiv datieren vom 22. und 23. März 2011 (erstinstanzliche Akten, 102 ff.).
Das Gerichtspräsidium Bremgarten verweist im Urteilsdispositiv vom 1. März 2011 auf die mit dem Inkrafttreten der Strafprozessordnung aufgehobene Bestimmung von § 168 aStPO/AG, wonach die Parteien innert 10 Tagen eine vollständige Ausfertigung des Urteils verlangen können, und das Urteil in Rechtskraft erwächst, wenn die Frist von keiner Partei benutzt wird.
1.6 Aus dem Grundsatz von Treu und Glauben (<ref-law>) ergibt sich, dass den Parteien aus einer unrichtigen Rechtsmittelbelehrung grundsätzlich keine Nachteile erwachsen dürfen. Den Vertrauensschutz kann eine Partei aber nicht beanspruchen, wenn sie die Unrichtigkeit der Rechtsmittelbelehrung erkannte oder bei gehörender Aufmerksamkeit hätte erkennen müssen (<ref-ruling>, 53 f.). Die rechtskundige Oberstaatsanwaltschaft musste wissen, dass die aargauische Strafprozessordnung mit dem Inkrafttreten der Schweizerischen Strafprozessordnung aufgehoben worden war, und sie hätte mit einem Blick ins Gesetz erkennen müssen, dass nach den massgebenden Übergangsbestimmungen das neue Recht anwendbar (<ref-law>) und demzufolge die Berufung innert 10 Tagen seit Eröffnung des Urteils anzumelden ist (<ref-law>). Sie kann sich deshalb nicht auf den Vertrauensschutz berufen.
1.7 Mit ihrer Eingabe an das Gerichtspräsidium Bremgarten vom 24. März 2011 stellte die Oberstaatsanwaltschaft ein blosses Motivierungsbegehren und ersuchte um Zustellung einer vollständig begründeten Ausfertigung des Urteils. Es fehlt jeder Hinweis darauf, dass sie auch den Willen hatte, die Berufung anzumelden. Nachdem sie offenbar noch von der Geltung des alten Rechts ausging, versäumte es die Oberstaatsanwaltschaft, eine den Anforderungen von <ref-law> genügende Erklärung abzugeben und mit der erforderlichen Klarheit festzuhalten, dass sie gegen das angefochtene Urteil die Berufung anmelden will (vgl. hierzu auch das Urteil 6B_170/2012 vom 7. Mai 2012 E. 1.4.2).
Das Urteilsdispositiv ging der Oberstaatsanwaltschaft spätestens am 22. März 2012 zu. Die Frist zur Anmeldung der Berufung lief folglich am 1. April 2011 ab. Die erst am 16. Mai 2011 eingereichte Berufungsanmeldung war verspätet. Die Oberstaatsanwaltschaft macht nicht geltend, sie sei unverschuldet nicht in der Lage gewesen, die Berufung rechtzeitig anzumelden.
1.8 Nachdem auf die Berufung der Oberstaatsanwaltschaft nicht eingetreten werden kann, fällt auch die Anschlussberufung der Privatklägerin dahin (<ref-law>).
2. Die Beschwerde erweist sich als begründet. Das Urteil des Obergerichts des Kantons Aargau vom 25. September 2012 ist aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Mit dem Entscheid in der Sache wird das Begehren um Gewährung der aufschiebenden Wirkung gegenstandslos.
Dem Ausgang des Verfahrens entsprechend sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Aargau hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Das Urteil des Obergerichts des Kantons Aargau vom 25. September 2012 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Es werden keine Kosten erhoben.
3. Der Kanton Aargau hat dem Beschwerdeführer eine Parteientschädigung von Fr. 3'000.-- auszurichten.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, Strafgericht, 2. Kammer, schriftlich mitgeteilt.
Lausanne, 11. April 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Keller