Sachverhalt:
A. X._ reiste am 25. April 2002 in die Schweiz ein und stellte in Vallorbe ein Asylgesuch. Das damals zuständige Bundesamt für Flüchtlinge (BFF) wies das Gesuch am 30. Oktober 2002 ab und ordnete die Wegweisung aus der Schweiz und den Vollzug an. Auf Beschwerde von X._ hin bestätigte die Schweizerische Asylrekurskommission (ARK) den Entscheid des BFF mit Urteil vom 18. Februar 2003. X._ wurde in der Folge wiederholt zum Verlassen der Schweiz aufgefordert, letztmals am 28. März 2008 nach Verbüssung einer Freiheitsstrafe von 90 Tagen wegen Widerhandlung gegen das Ausländergesetz im Sinne von Art. 115 Abs. 1 lit. b AuG.
Mit Anklageschrift vom 17. Dezember 2010 wird X._ vorgeworfen, er habe sich von Anfang April 2008 bis zum 6. Dezember 2010 in der Schweiz aufgehalten, obwohl er aufgrund der rechtskräftigen Abweisung des Asylgesuchs und der Anordnung der Wegweisung gewusst habe, dass er das Land seit dem 30. Oktober 2002 hätte verlassen müssen. Stattdessen habe er sich weiterhin hier aufgehalten, den Behörden eine falsche Nationalität angegeben und sich keine Reisepapiere beschafft, obwohl ihm dies möglich gewesen wäre.
B. Der Einzelrichter des Bezirksgerichts Zürich sprach X._ am 10. Februar 2011 wegen illegalen Aufenthalts im Sinne von Art. 115 Abs. 1 lit. b AuG schuldig und bestrafte ihn mit einer unbedingten Freiheitsstrafe von sechs Monaten. Gegen diesen Entscheid legte X._ Berufung beim Obergericht des Kantons Zürich ein, welches ihn mit Urteil vom 5. September 2011 von Schuld und Strafe freisprach.
C. Die Oberstaatsanwaltschaft des Kantons Zürich wendet sich mit Beschwerde in Strafsachen an das Bundesgericht. Sie beantragt, das obergerichtliche Urteil vom 5. September 2011 sei wegen Verletzung von Bundesrecht aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
D. Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1. 1.1 Wer sich rechtswidrig, namentlich nach Ablauf des bewilligungsfreien oder des bewilligten Aufenthalts, in der Schweiz aufhält, wird mit Freiheitsstrafe bis zu einem Jahr oder mit Geldstrafe bestraft (Art. 115 Abs. 1 lit. b AuG).
1.2 Es ist unbestritten, dass der Beschwerdegegner sich im Zeitraum von Anfang April 2008 bis zum 6. Dezember 2010 wissentlich und willentlich ohne Aufenthaltstitel in der Schweiz aufgehalten hat. Sein Asylgesuch wurde rechtskräftig abgewiesen, die Wegweisung definitiv verfügt und er wiederholt, letztmals am 28. März 2008, zum Verlassen der Schweiz aufgefordert.
1.3 Für die Strafbarkeit des rechtswidrigen Verweilens nach Art. 115 Abs. 1 lit. b AuG muss in jedem Fall vorausgesetzt werden, dass es der betroffenen ausländischen Person - etwa aufgrund einer Weigerung des Heimatlands, Staatsangehörige zurückzunehmen oder Ausweispapiere auszustellen (vgl. <ref-ruling> E. 4.1.3; <ref-ruling> E. 2) - objektiv nicht unmöglich ist, legal aus der Schweiz auszureisen bzw. rechtmässig in das Heimatland zurückzukehren. Andernfalls kann ihr der Normverstoss nicht zur Last gelegt werden bzw. darf sie wegen rechtswidrigen Aufenthalts nicht bestraft werden. Das strafrechtliche Schuldprinzip setzt die Freiheit voraus, anders handeln zu können (Urteile des Bundesgerichts 6B_482/2010 vom 7. Oktober 2010 E. 3.2.2 und 6B_85/2007 vom 3. Juli 2007 E. 2.3).
1.4 1.4.1 Nach den Feststellungen der Vorinstanz konnte die Identität des Beschwerdegegners nicht mittels eines Ausweispapieres festgestellt werden. Dieser hielt jedoch stets daran fest, Angolaner zu sein. Bei den Akten des Migrationsamts liegt denn auch eine entsprechende Geburtsurkunde des Beschwerdegegners in Kopie. Der angolanische Staat hat diesen indessen anlässlich von zwei Befragungen in den Jahren 2006 und 2008 nicht als Staatsangehörigen anerkannt. Die Gründe hierfür sind den Akten nicht zu entnehmen. Auch wenn nicht auszuschliessen ist, dass der Beschwerdegegner die hiesigen Behörden über seine wahre Herkunft täuscht, kann ihm solches nach den unangefochten gebliebenen Feststellungen im angefochtenen Entscheid (S. 8) nicht nachgewiesen werden. Die Vorinstanz nimmt daher an, der Beschwerdegegner sei angolanischer Staatsangehöriger. Die Beschwerdeführerin beanstandet diesen Schluss zu Recht nicht als willkürlich (vgl. Beschwerde, S. 4).
1.4.2 Ist davon auszugehen, der Beschwerdegegner sei Angolaner, steht die Weigerung des angolanischen Staates, ihn als solchen anzuerkennen und entsprechende Identitäts- und Reisepapiere auszustellen, einer rechtmässigen Ausreise des Beschwerdegegners in sein Heimatland entgegen. Von ihm kann nach rechtsstaatlichen Grundsätzen auch keine illegale Ausreise in einen Drittstaat verlangt werden (<ref-ruling> E. 4.2.2). Mit andern Worten war es dem Beschwerdegegner objektiv unmöglich, die Schweiz legal zu verlassen. Der Normverstoss kann ihm unter diesen Umständen nicht zur Last gelegt werden. Das ergibt sich bereits aus der bisherigen Rechtsprechung zu Art. 115 Abs. 1 lit. b AuG (bzw. Art. 23 Abs. 1 al. 4 ANAG). Zwar bejahte das Bundesgericht im Urteil 6B_85/2007 vom 3. Juli 2007 die Strafbarkeit des illegalen Verweilens trotz objektiver Unmöglichkeit der legalen Rückreise in das Heimatland, das allerdings nur, weil der illegal anwesende Ausländer in der Schweiz untergetaucht war (und sich in der Folge nicht um die Legalisierung seines Status bemüht hatte). Eine solche Konstellation liegt hier nicht vor. Die Frage, ob und inwiefern der Beschwerdegegner sich trotz bereits zweifacher Ablehnung durch den angolanischen Staat weiterhin um die Anerkennung der Staatsangehörigkeit bei den angolanischen Behörden sowie bei anderen Institutionen/Organisationen und die Beschaffung von Reisepapieren hätte bemühen müssen, stellt sich daher entgegen der Annahme in der Beschwerde (S. 4 ff.) nicht im Zusammenhang mit dem Vorwurf des illegalen Aufenthalts nach Art. 115 Abs. 1 lit. b AuG, sondern einzig im Hinblick auf eine allfällige Pflicht des Beschwerdegegners, bei der Beschaffung von Ausweispapieren mitzuwirken (Art. 120 Abs. 1 lit. e AuG). Eine solche Pflichtverletzung wird dem Beschwerdegegner unter Berücksichtigung der Weigerung des angolanischen Staates, ihn als Staatsangehörigen anzuerkennen und Papiere auszustellen, in der Anklageschrift allerdings nicht formell zur Last gelegt (vgl. Anklageschrift vom 17. Dezember 2010, S. 2). Da nicht Verfahrensgegenstand, ist nicht zu klären, inwiefern der Beschwerdegegner gegen eine ihm diesbezüglich allenfalls obliegende Pflicht verstossen haben könnte.
1.4.3 Der vorinstanzliche Freispruch des Beschwerdegegners vom Vorwurf des illegalen Aufenthalts ist bundesrechtlich nicht zu beanstanden. Die Beschwerde ist abzuweisen. Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und Abs. 4 BGG). Dem Beschwerdegegner ist keine Entschädigung zuzusprechen, da ihm im bundesgerichtlichen Verfahren keine Umtriebe erwachsen sind.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 2. März 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill