Sachverhalt: A. Die stark alkoholisierte X._, eine brasilianische Staatsangehörige, wurde am 28. Januar 2011, um 07.15 Uhr, durch die Kantonspolizei Zürich in der "A._-Bar", einer "Kontaktbar" im Kerngebiet des Stadtzürcher Milieus, angehalten. Da sie sich nicht ausweisen konnte (und wollte) und die Polizeibeamten in ihrer Handtasche keine Ausweispapiere fanden, wurde sie auf den Polizeiposten geführt. Im Zuge der auf dem Posten durchgeführten Durchsuchung wurden ein "Chip der Swisscom" und ein "I-Phone" gefunden sowie "offensichtliche Freier-Adressen", die darauf hinwiesen, X._ sei ohne Bewilligung als Prostituierte erwerbstätig. Gestützt auf diese Daten kontaktierten die Polizeibeamten den späteren Zeugen B._. Dieser gab an, mit X._ Sexualverkehr gegen Geld gehabt zu haben. B. Das Obergericht des Kantons Zürich sprach X._ zweitinstanzlich am 9. März 2012 des rechtswidrigen Aufenthalts und der Erwerbstätigkeit ohne Bewilligung gemäss Art. 115 Abs. 1 lit. b und c des Bundesgesetzes über die Ausländerinnen und Ausländer (AuG; SR 142.20) schuldig. In Bezug auf den Freispruch vom Vorwurf der Widerhandlung gegen Art. 115 Abs. 1 lit. a AuG (Verletzung von Einreisevorschriften) stellte es die Rechtskraft des Urteils des Bezirksgerichts Zürich vom 7. März 2011 fest. Es bestrafte X._ mit 45 Tagen Freiheitsstrafe (wovon alle Tage durch Untersuchungs- und Sicherheitshaft erstanden sind). Den Vollzug der Freiheitsstrafe schob es nicht auf. Das Obergericht sprach X._ keine Genugtuung zu und auferlegte ihr die Kosten des Berufungsverfahrens. Die erstinstanzliche Kostenregelung bestätigte es. C. Mit Beschwerde in Strafsachen beantragt X._, sie sei vom Vorwurf der mehrfachen Widerhandlung gegen das Ausländergesetz freizusprechen, und die Kosten des kantonalen Verfahrens seien auf die Gerichtskasse zu nehmen. Für die erlittene Untersuchungs- und Sicherheitshaft sei ihr eine Genugtuung von mindestens Fr. 4'500.-- zuzusprechen. Eventuell sei das Urteil des Obergerichts aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung. D. Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich haben auf eine Stellungnahme zur Beschwerde verzichtet. 