Sachverhalt:
A. A._ (geb. 1992) und B._ (geb. 1995) waren erfolgreiche Mitglieder der Geräteriege D._. Am 2. August 2007 trat ihr Trainer C._ aufgrund diverser Meinungsverschiedenheiten per sofort zurück. Im Rahmen der Neuorganisation der Geräteriege kam es zu weiteren Spannungen. Insbesondere die beiden Mädchen hatten Mühe, sich mit der neuen Situation abzufinden. Nachdem sie mehrmals die Trainingsmethoden der neuen Trainer kritisiert und sich über mangelnde Unterstützung beklagt hatten, gingen sie privat bei C._ trainieren. In der Folge wurden die beiden mündlich verwarnt und vom Training suspendiert. Am 13. März 2008 schickte der Vorstand der Geräteriege, vertreten durch X._, den beiden Turnerinnen und deren Eltern eine Erklärung mit der Androhung, die beiden Mädchen aus der Geräteriege auszuschliessen, wenn die Erklärung nicht unterzeichnet und die darin enthaltenen Regeln nicht eingehalten würden. Nachdem sich die Mädchen (und ihre Eltern) weigerten, die Erklärung zu unterzeichnen, wurden beide per sofort aus der Geräteriege ausgeschlossen. Unterzeichnet wurde die "Ausschlussverfügung" von X._ und der Präsidentin des Damen- und Frauenturnvereins D._, Y._.
B. Am 30. November/7. Dezember 2010 sprach das Landgericht Uri X._ und Y._ der in Mittäterschaft begangenen versuchten Nötigung schuldig und verurteilte beide zu einer bedingten Geldstrafe von 5 Tagessätzen zu Fr. 30.--. Die Probezeit setzte es auf 2 Jahre fest. Die Schadenersatz- und Genugtuungsforderungen von A._ und B._ wurden auf den Zivilweg verwiesen. Die gegen dieses Urteil gerichtete Berufung von X._ und Y._ hiess das Obergericht des Kantons Uri am 15. März 2012 gut. Es sprach sie vom Vorwurf der Nötigung frei.
C. Die Staatsanwaltschaft des Kantons Uri führt Beschwerde in Strafsachen. Sie verlangt, die beiden Urteile des Obergerichts aufzuheben und X._ sowie Y._ wegen versuchter Nötigung schuldig zu sprechen. Sie seien mit einer bedingten Geldstrafe von 5 Tagessätzen zu Fr. 30.--, bei einer Probezeit von 2 Jahren, zu bestrafen. Eventualiter sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
D. Das Obergericht des Kantons Uri verzichtet auf eine Vernehmlassung. X._ und Y._ beantragen die kostenfällige Abweisung der Beschwerde.

Erwägungen:
1. Die Beschwerden betreffen denselben Sachverhalt und richten sich gegen zwei inhaltlich gleiche Urteile. Die Verfahren 6B_540/2012 und 6B_541/2012 sind zu vereinigen (<ref-law> i.V.m. <ref-law>).
2. 2.1 Die Vorinstanz leitet aus ihren Sachverhaltsfeststellungen ab, dass es am Tatbestandselement des ernsthaften Nachteils mangelt, weshalb keine Nötigung nach <ref-law> vorliegt (Urteil, S. 11 f.). Im Sinne einer Eventualbegründung bejaht sie einen nicht vermeidbaren Verbotsirrtum gemäss <ref-law> (Urteil, S. 13 f.).
2.2 Ein Verbotsirrtum nach <ref-law> liegt vor, wenn der Täter nicht weiss und nicht wissen kann, dass er sich rechtswidrig verhält. War der Irrtum vermeidbar, so mildert das Gericht die Strafe (<ref-law>). Was der Täter wusste, wollte und in Kauf nahm, betrifft innere Tatsachen (<ref-ruling> E. 4.2.3; <ref-ruling> E. 3c S. 252; je mit Hinweisen), welche das Bundesgericht nur unter dem Gesichtspunkt der Willkür prüft (<ref-law>).
2.3 Die Beschwerdeführerin bezeichnet die Eventualbegründung der Vorinstanz als nicht nachvollziehbar. Die Beschwerdegegnerinnen hätten sich zumindest in einem vermeidbaren Verbotsirrtum befunden. Sie hätten erkennen müssen oder juristische Abklärungen treffen können, dass die Erklärung in unzulässiger Weise in die Privatsphäre der betroffenen Mädchen und deren Eltern eingreife (Beschwerde, S. 6 f.).
2.4 Die Beschwerde in Strafsachen ist zu begründen. Beruht der Entscheid wie hier auf mehreren selbständigen Begründungen, die je für sich den Ausgang des Rechtsstreits besiegeln, so hat die Beschwerdeführerin darzulegen, dass jede von ihnen Recht verletzt (<ref-ruling> E. 6.3). Die Beschwerdeführerin wendet sich zwar gegen die vorinstanzliche Haupt- und Eventualbegründung. Sie beanstandet jedoch nicht die Sachverhaltsfeststellungen in Bezug auf <ref-law> und zeigt nicht auf, inwiefern die Vorinstanz willkürlich einen nicht vermeidbaren Verbotsirrtum bejaht hat. Was sie gegen die tatsächlichen Feststellungen einwendet, erschöpft sich in einer appellatorischen Kritik, die den Begründungsanforderungen gemäss <ref-law> nicht genügt.
3. Auf die Beschwerden ist nicht einzutreten. Dem Kanton Uri sind keine Gerichtskosten aufzuerlegen (<ref-law>). Die Beschwerdegegnerinnen obsiegen, da es beim Freispruch vom Vorwurf der Nötigung bleibt. Der Kanton Uri hat ihnen eine angemessene Entschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Verfahren 6B_540/2012 und 6B_541/2012 werden vereinigt.
2. Auf die Beschwerden wird nicht eingetreten.
3. Es werden keine Kosten erhoben.
4. Der Kanton Uri hat der Beschwerdegegnerin 1 und der Beschwerdegegnerin 2 eine Parteientschädigung von je Fr. 1'500.-- auszurichten.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Uri, Strafrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 7. März 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Keller