Das Bundesgericht zieht in Erwägung:
1. Die Vorinstanz sprach den Beschwerdeführer am 15. November 2011 im Appellationsverfahren des Diebstahls, des mehrfachen geringfügigen Diebstahls sowie des rechtswidrigen Aufenthalts schuldig und bestrafte ihn mit einer Freiheitsstrafe von 90 Tagen sowie einer Busse von Fr. 100.-- bzw. einer Ersatzfreiheitsstrafe von einem Tag. Ein früher gewährter bedingter Vollzug für eine Freiheitsstrafe von sechs Monaten wurde widerrufen.
Der Beschwerdeführer wendet sich ans Bundesgericht und beantragt sinngemäss einen Freispruch und eventuell eine geringere Strafe.
2. Vor Bundesgericht angefochten werden kann nur das Urteil der Vorinstanz (<ref-law>). Soweit sich der Beschwerdeführer mit Strafverfügungen des Amtsstatthalteramts oder einer ihm drohenden Ausweisung befasst (Beschwerde Ziff. 6-9), ist darauf nicht einzutreten.
3. Der Beschwerdeführer rügt, er habe vor der Vorinstanz seine Lage nicht hinreichend erklären können (Beschwerde Ziff. 2). Indessen führte die Vorinstanz eine Verhandlung durch, in welcher der Beschwerdeführer seinen in der Appellationserklärung gestellten Antrag abänderte (vgl. angefochtenen Entscheid S. 5 lit. E und F). Inwieweit ihm das rechtliche Gehör nicht ausreichend gewährt worden sein könnte, ist nicht ersichtlich.
4. Der Beschwerdeführer macht geltend, für die ihm vorgeworfenen Diebstähle gebe es keine konkreten und "überwältigenden" Beweise (Beschwerde Ziff. 4). Die Beweiswürdigung kann vor Bundesgericht indessen nur gerügt werden, wenn sie offensichtlich unrichtig im Sinne von <ref-law> bzw. willkürlich im Sinne von <ref-law> ist. Willkür liegt vor, wenn der angefochtene Entscheid im bemängelten Punkt offensichtlich unhaltbar ist oder mit der tatsächlichen Situation in klarem Widerspruch steht. Dass eine andere Lösung ebenfalls vertretbar erscheint, genügt nicht (<ref-ruling> E. 2.4). Die angebliche Willkür ist präzise zu rügen, und die Rüge ist zu begründen (<ref-law>). Die Behauptung, es gebe für die Verurteilung keine hinreichenden Beweise, genügt als Begründung einer Willkürrüge nicht.
5. Der Beschwerdeführer macht geltend, seine Verurteilung wegen rechtswidrigen Aufenthalts widerspreche der Rechtsprechung des Gerichtshofes der europäischen Union (Beschwerde S. 1). Nationale Strafbestimmungen sind indessen dort nicht ausgeschlossen, wo im verwaltungsrechtlichen Verfahren alles für den Vollzug der Rückkehrentscheidung Zumutbare vorgekehrt worden ist, dieser indessen am Verhalten des Betroffenen scheitert (EuGH-Urteil C-329/11 vom 6. Dezember 2011 i.S. Achughbabian, N 46-50; THOMAS HUGI YAR, Das Urteil El Dridi, die EU-Rückführungsrichtlinie und der Schengen-Besitzstand, in: Jusletter 11. Juli 2011, Rz 11). Im vorliegenden Fall scheitert die Rückführung nach den Feststellungen der Vorinstanz daran, dass der Beschwerdeführer nicht bereit ist, bei der Beschaffung der erforderlichen Reisepapiere mitzuwirken (angefochtener Entscheid S. 8 E. 4.4). Folglich ist sein Einwand bereits aus diesem Grund nicht zu hören.
6. Gemäss <ref-law> misst das Gericht die Strafe nach dem Verschulden des Täters zu. Es berücksichtigt das Vorleben, die persönlichen Verhältnisse und die Wirkung der Strafe auf das Leben des Täters. Die Bewertung des Verschuldens richtet sich gemäss Abs. 2 derselben Bestimmung nach der Schwere der Verletzung oder der Gefährdung des betroffenen Rechtsguts, nach der Verwerflichkeit des Handelns, den Beweggründen und Zielen des Täters sowie danach, wie weit er nach den innern und äussern Umständen in der Lage war, die Gefährdung oder Verletzung zu vermeiden. Es liegt im Ermessen des Sachgerichts, in welchem Umfang es den verschiedenen Strafzumessungsfaktoren Rechnung trägt. Das Bundesgericht greift nur ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen bzw. in Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet hat (<ref-ruling> E. 2.1 mit Hinweisen).
Der Beschwerdeführer macht geltend, sein Strafregister sei bis 2011 in Ordnung gewesen (Beschwerde Ziff. 5). Dies trifft nicht zu. Bereits am 27. Februar 2008 wurde er unter anderem wegen Hehlerei und mehrfachen Diebstahls zu einer bedingten Freiheitsstrafe von sechs Monaten verurteilt (angefochtener Entscheid S. 7 E. 4.4). Dieser Umstand wurde zu Recht straferhöhend gewichtet.
Weiter macht der Beschwerdeführer geltend, der Vollzug der Freiheitsstrafe belaste die Beziehung zu seinen Töchtern (Beschwerde Ziff. 3). Die Verbüssung einer Freiheitsstrafe ist indessen für jeden in ein familiäres Umfeld eingebetteten Beschuldigten mit einer gewissen Härte verbunden. Als unmittelbare gesetzmässige Sanktion darf diese Konsequenz nur bei aussergewöhnlichen Umständen erheblich strafmindernd wirken (Urteil 6B_449/2011 vom 12. September 2011 E. 3.5). Solche Umstände sind nicht ersichtlich.
Insgesamt ist die Strafzumessung nicht zu beanstanden.
7. Die Beschwerde ist im Verfahren nach <ref-law> abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege (Beschwerde Ziff. 10) ist in Anwendung von <ref-law> abzuweisen, weil die Rechtsbegehren aussichtslos erschienen. Der finanziellen Lage des Beschwerdeführers (vgl. angefochtenen Entscheid S. 8 E. 4.5) ist bei der Bemessung der Gerichtskosten Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Luzern, 4. Abteilung, schriftlich mitgeteilt.
Lausanne, 17. April 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: C. Monn