Sachverhalt: A. Das Landgericht Uri sprach X._ am 22. Januar 2008 des mehrfachen Erleichterns des rechtswidrigen Verweilens im Lande gemäss Art. 23 Abs. 1 al. 5 ANAG schuldig und verurteilte ihn zu einer Geldstrafe von 20 Tagessätzen zu Fr. 70.--, bedingt vollziehbar bei einer Probezeit von zwei Jahren, und zu einer Busse von Fr. 1000.-- beziehungsweise, bei deren schuldhaften Nichtbezahlung, zu einer Ersatzfreiheitsstrafe von zehn Tagen. Das Landgericht erachtete es als erwiesen, dass X._ im April 2004 drei Ausländerinnen aus Ungarn beziehungsweise aus Tansanien, die sich als Touristinnen in der Schweiz aufhielten, in seinem Gastwirtschaftsbetrieb in Erstfeld, zu welchem die B.-Bar_ gehörte, Zimmer vermietete im Wissen darum, dass die drei Frauen, die nicht über die erforderlichen Bewilligungen verfügten, in seinem Betrieb der Prostitution nachgingen. Das Landgericht stützte seine tatsächlichen Feststellungen unter anderem auf die Aussagen des Polizeibeamten A._, der sich im Auftrag seines Vorgesetzten am 14. April 2004, ab ca. 23.45 Uhr, in der B.-Bar_ aufgehalten hatte, wo ihm von einer der dort anwesenden Frauen die Vornahme von sexuellen Handlungen gegen Zahlung von Geld angeboten worden war, was A._ abgelehnt hatte. Das Obergericht des Kantons Uri sprach X._ auf dessen Berufung hin am 31. März 2009 frei. Es begründete diesen Freispruch unter anderem damit, dass die durch den Einsatz des Polizeibeamten A._ gewonnenen Erkenntnisse nicht verwertbar seien. B. Die Staatsanwaltschaft des Kantons Uri führt Beschwerde in Strafsachen mit dem Antrag, das Urteil des Obergerichts sei aufzuheben, X._ sei des mehrfachen Erleichterns des rechtswidrigen Verweilens im Lande im Sinne von Art. 23 Abs. 1 al. 5 ANAG schuldig zu sprechen und zu einer bedingt vollziehbaren Geldstrafe von 20 Tagessätzen zu Fr. 70.-- sowie zu einer Busse von Fr. 1000.-- zu verurteilen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Das Obergericht des Kantons Uri hat auf Vernehmlassung verzichtet. X._ beantragt die Abweisung der Beschwerde. 