Sachverhalt:
A. X._ wird im Wesentlichen vorgeworfen, er habe ab September 2004 zu Unrecht eine Invalidenrente der Sozialversicherungsanstalt des Kantons Zürich (nachfolgend: SVA) sowie eine Komplementärrente der A._ Versicherungen (nachfolgend: A._) nach dem Bundesgesetz vom 20. März 1981 über die Unfallversicherung (UVG, SR 832.20) bezogen. Konkret habe er es unterlassen, die Versicherer über seine Arbeitstätigkeit als faktisch vollamtlicher Geschäftsführer der in Bratislava (Slowakei) domizilierten B._ GmbH orientiert zu haben. Überdies habe er in einem Fragebogen gegenüber der SVA sowie in einem protokollierten Gespräch mit der A._ wahrheitswidrige Angaben gemacht.
Die A._ liess X._ nach einem telefonischen Hinweis sowie nach internen Vorabklärungen ab April 2007 observieren. Diese Beobachtungen mündeten in zwei Observationsberichte vom 29. September 2007 und 17. Dezember 2007.
B. Das Bezirksgericht Dietikon verurteilte X._ am 10. Februar 2009 wegen mehrfachen Betrugs sowie versuchten Betrugs zu einer Freiheitsstrafe von 24 Monaten. Den Vollzug der Freiheitsstrafe schob es im Umfang von zwölf Monaten, bei einer Probezeit von drei Jahren, auf. Die übrigen zwölf Monate erklärte es unter Anrechnung von 87 Tagen Untersuchungshaft als vollziehbar. Die Zivilforderung der A._ verwies es auf den Zivilweg.
Das Obergericht des Kantons Zürich sprach X._ am 24. März 2011 auf dessen Berufung hin frei. Auf die Zivilforderung der A._ trat es nicht ein.
C. Die Oberstaatsanwaltschaft des Kantons Zürich erhebt Beschwerde in Strafsachen beim Bundesgericht. Sie beantragt, das Urteil des Obergerichts des Kantons Zürich aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
D. Das Obergericht des Kantons Zürich verzichtet auf eine Vernehmlassung. X._ beantragt, die Beschwerde der Oberstaatsanwaltschaft des Kantons Zürich sei abzuweisen, und ihm sei für das vorliegende Verfahren eine angemessene Prozessentschädigung zuzusprechen, sofern das Begehren um unentgeltliche Rechtspflege nicht bewilligt werde.

Erwägungen:
1. 1.1 Die Vorinstanz erachtet die Angaben des Beschwerdegegners zu den Gründen seiner Tätigkeit in der B._ GmbH als nicht überzeugend und unglaubhaft. Seine Erklärung, wonach er dort jeweils ein bis zwei Stunden anwesend gewesen sei, um zum Rechten zu schauen, seien durch die Observationen widerlegt worden. Zudem bestehe ein deutlicher Unterschied zwischen seinen Angaben im SVA-Fragebogen und im Gesprächsprotokoll der A._ einerseits sowie den Observationsergebnissen andererseits. Auch liessen sich die Aussagen seiner Lebenspartnerin zur Häufigkeit seiner Tätigkeit in der B._ GmbH in keiner Weise mit den Observationsergebnissen vereinbaren und seien insgesamt wenig glaubhaft (angefochtenes Urteil, S. 30 ff.).
Die Vorinstanz bezeichnet die erstinstanzliche Schlussfolgerung aus der Beweiswürdigung als unhaltbar, wonach der Beschwerdegegner seit dem 27. August 2004 als faktischer Geschäftsführer der B._ GmbH tätig gewesen sei und ein in der Höhe nicht bekanntes Einkommen bezogen habe. Seine Tätigkeit sei lediglich für die Tage der Observation rechtsgenügend erstellt. Seit wann und in welchem Umfang er in der B._ GmbH tätig gewesen sei, lasse sich aufgrund der vorliegenden Beweislage jedoch nicht zweifelsfrei erstellen. Die Observation habe insgesamt lediglich 32 Tage gedauert, wobei der Beschwerdegegner an einem Fünftel der Tage nicht in den Geschäftsräumlichkeiten der B._ GmbH anzutreffen gewesen sei. Nicht nachweisbar sei auch der Vorwurf in der Anklageschrift, wonach er ein in der Höhe nicht bekanntes Einkommen bezogen habe (angefochtenes Urteil, S. 34 f.).
Die Vorinstanz führt weiter aus, der Beschwerdegegner sei verpflichtet gewesen, die Versicherer über seine Tätigkeit für die B._ GmbH zu unterrichten. Dies hätte zu einer Neuberechnung der Rente geführt. Entgegen der Anklage könne jedoch nicht ohne weiteres davon ausgegangen werden, dass diese Rentenrevision zur Aufhebung der Rentenzahlung geführt hätte. Auch die erstinstanzliche Auffassung, wonach er zumindest nicht Rentenleistungen in der bisher ausbezahlten Höhe erhalten hätte, sei eine Mutmassung, da im Rahmen der Untersuchung nicht geklärt worden sei, zu welchem Ergebnis eine Rentenrevision geführt hätte. Eine solche Revision bzw. Neuberechnung der Rente finde im sozialversicherungsrechtlichen Verfahren statt. Die Anklageerhebung hätte daher sinnvollerweise erst nach rechtskräftiger Neuberechnung der Rente erfolgen sollen. Das Tatbestandselement des Schadens könne vorliegend weder beziffert werden noch stehe fest, ob nach einer Rentenrevision von einem Schaden gesprochen werden könne. Dies gelte umso mehr, als der Beschwerdegegner zwar eine volle IV-Rente beziehe, in seinem angestammten Beruf oder unter gewissen Voraussetzungen auch bei anderen Tätigkeiten jedoch bis zu 30 % arbeitsfähig sei. Eine ungerechtfertigte Bereicherung des Beschwerdegegners bzw. ein unrechtmässiger Vermögensschaden bei den Versicherern sei nicht rechtsgenügend erstellt, weshalb er von den Anklagevorwürfen freizusprechen sei (angefochtenes Urteil, S. 35 ff.).
1.2 Die Beschwerdeführerin wendet sich gegen den vorinstanzlichen Freispruch. Es könne nicht sein, dass generell ein Schaden nicht nachgewiesen werden könne, wenn ein Versicherter in Verletzung seiner Pflichten Faktoren verschweige, die zu einem Wegfall oder einer Kürzung der Rente führen müssten. Dies würde in Fällen wie dem vorliegenden zum stossenden Ergebnis führen, dass ein Versicherter, der neben den Versicherungsleistungen ein Erwerbseinkommen erziele, nicht bestraft werden könne, weil er über keinen Lohnausweis verfüge und mangels verbindlicher Angaben über den tatsächlichen Verdienst eine Rentenrevision auch hypothetisch nicht möglich sei (Beschwerde, S. 3 f.).
Die Vorinstanz verkenne, dass die Bereicherung beim Betrug nicht einzutreten brauche, sondern eine diesbezügliche Absicht des Täters genüge. Der Betrugstatbestand sei zudem als Erfolgsdelikt konzipiert, wobei der Vermögensschaden den Erfolg darstelle. Wenn der Erfolg nicht eingetreten sei, hätte zusätzlich geprüft werden müssen, ob ein Versuch im Sinne von <ref-law> vorliege, was die Vorinstanz unterlassen habe (Beschwerde, S. 4).
Der Beschwerdegegner habe subjektiv in Bezug auf sämtliche objektiven Tatbestandsmerkmale des Betrugs (arglistige Täuschung, Irrtum, Vermögensdisposition und Vermögensschaden) zumindest eventualvorsätzlich gehandelt. Er habe damit rechnen müssen, dass eine Rentenrevision eine tiefere Rente oder deren vollständigen Verlust zur Folge gehabt hätte. Er habe daher in Kauf genommen, dass die Versicherer durch das Verschweigen seiner Erwerbstätigkeit eine zu hohe Rente zahlten und er im Gegenzug ungerechtfertigt bereichert werde. Selbst wenn man annehme, ein Vermögensschaden sei objektiv nicht möglich, läge ein - ebenfalls strafbarer - untauglicher Versuch vor (Beschwerde, S. 4 f.).
1.3 Dem Sachgericht steht im Bereich der Beweiswürdigung ein erheblicher Ermessensspielraum zu (<ref-ruling> E. 6.1 mit Hinweisen; <ref-ruling> E. 4b). Das Bundesgericht greift auf Beschwerde hin nur ein, wenn das Sachgericht diesen missbraucht, insbesondere offensichtlich unhaltbare Schlüsse zieht, erhebliche Beweise übersieht oder solche willkürlich ausser Acht lässt (<ref-ruling> E. 2.1). Inwiefern das kantonale Gericht sein Ermessen im dargelegten Sinn missbraucht haben soll, ist in der Beschwerde klar und detailliert aufzuzeigen (<ref-ruling> E. 1.3).
1.4 Die Vorinstanz gibt die zwei Observationsberichte, die Stellungnahmen des Beschwerdegegners dazu sowie seine weiteren Aussagen umfassend wieder (angefochtenes Urteil, S. 11-21 sowie S. 23 f.). Ebenso geht sie ausführlich auf die medizinischen Berichte und Zeugenaussagen der behandelnden Ärzte sowie auf den Inhalt des SVA-Fragebogens und des Gesprächs mit der A._ ein (angefochtenes Urteil, S. 21 f. und S. 24-27). Schliesslich fasst sie die Aussagen der Lebenspartnerin des Beschwerdegegners zusammen (angefochtenes Urteil, S. 28 f.).
Grundlage einer Verurteilung bildet ein Beweisergebnis, wonach der Beschuldigte mit an Sicherheit grenzender Wahrscheinlichkeit das inkriminierte Verhalten verwirklicht hat. Die Observation des Beschwerdegegners fand gemäss Vorinstanz an lediglich 32 Tagen im Jahre 2007 statt, wobei dieser zudem an einem Fünftel dieser Tage nicht in der B._ GmbH erschienen ist. Es ist nicht zu beanstanden, wenn die Vorinstanz die angebliche Tätigkeit des Beschwerdegegners als faktischer Geschäftsführer der B._ GmbH ab dem 27. August 2004 - mithin bereits rund drei Jahre früher - als nicht rechtsgenügend erstellt erachtet, zumal aufgrund der bestehenden Beweislage unklar bleibt, seit wann und in welchem Umfang dieser in der B._ GmbH tätig war und welches Einkommen er dabei erzielt hatte. Aufgrund des Beweisergebnisses lässt sich der Betrugstatbestand nicht bejahen, da weder eine Bereicherungsabsicht des Beschwerdegegners noch eine Vermögensschädigung der Versicherer dargetan ist.
Die Vorinstanz zieht aus diesem Beweisergebnis jedoch den unzutreffenden Schluss, der Beschwerdegegner sei freizusprechen. Die Vorinstanz wäre vielmehr gehalten gewesen, den Sachverhalt näher abzuklären.
1.5 Es steht fest, dass der Beschwerdegegner die Versicherer von seiner Tätigkeit in der B._ GmbH hätte unterrichten müssen. Diese nach der Strafbestimmung von Art. 113 des Bundesgesetzes vom 20. März 1981 über die Unfallversicherung (UVG) strafrechtlich relevante Unterlassung hätte zu einer Neuberechnung der Rente durch die Versicherer geführt. Die Beschwerdeführerin argumentiert in diesem Zusammenhang zu Unrecht, ein Schaden könne generell nicht nachgewiesen werden, sofern ein Versicherter erwerbsrelevante Faktoren gegenüber dem Versicherer aus Pflichtverletzung verschweigt. Vielmehr hätte es an den Untersuchungsbehörden gelegen, den tatsächlichen Schaden zu berechnen. Die Anklageerhebung hätte daher, worauf die Vorinstanz hinweist, mit Vorteil erst nach der rechtskräftigen Neufestlegung der Rente erfolgen sollen.
Das bedeutet entgegen der Vorinstanz jedoch nicht, dass das Resultat dieser Rentenrevision offenzubleiben hat, weil im Rahmen der Strafuntersuchung das Ergebnis einer solchen Rentenrevision nicht berechnet wurde. Da der Beschwerdegegner zwar eine volle IV-Rente bezog, jedoch gleichzeitig als bis zu 30 % arbeitsfähig eingestuft wurde, konnte die Vorinstanz zwar zu Recht nicht automatisch auf eine teilweise oder vollständige Aufhebung der Rentenzahlung schliessen. Sie hätte jedoch eine Rentenrevision bzw. eine Neuberechnung der Rente durch die zuständigen Behörden in die Wege leiten können und müssen.
1.6 Nach <ref-law> müssen beim Bundesgericht anfechtbare Entscheide die massgebenden Gründe tatsächlicher und rechtlicher Art enthalten und insbesondere die massgeblichen Gesetzesbestimmungen angeben. Der vorinstanzliche Entscheid muss somit aufzeigen, auf welchem festgestellten Sachverhalt er beruht und welches die auf den Sachverhalt angewendeten rechtlichen Überlegungen sind (<ref-ruling> E. 8.2). Nach der bundesgerichtlichen Rechtsprechung ist die Begründung insbesondere mangelhaft, wenn der angefochtene Entscheid jene tatsächlichen Feststellungen nicht trifft, die zur Überprüfung des eidgenössischen Rechts notwendig sind oder wenn die rechtliche Begründung des angefochtenen Entscheides so lückenhaft oder unvollständig ist, dass nicht geprüft werden kann, wie das eidgenössische Recht angewendet wurde. Die Begründung ist ferner mangelhaft, wenn einzelne Tatbestandsmerkmale, die für die Subsumtion unter eine gesetzliche Norm von Bedeutung sind, von der Vorinstanz nicht oder nicht genügend abgeklärt wurden (<ref-ruling> E. 5b mit Hinweis).
1.7 Die Vorinstanz kommt im vorliegenden Fall ihrer Begründungspflicht insofern nicht nach, als sie - wie aufgezeigt - mehrere notwendige Sachverhaltsfeststellungen nicht vorgenommen hat bzw. nicht hat vornehmen lassen. Der Betrugsvorwurf lässt sich gestützt auf das bisherige Sachverhaltsfundament nicht auf seine Richtigkeit überprüfen, weshalb die Vorinstanz mit ihrem Freispruch des Beschwerdegegners vom Vorwurf des mehrfachen Betrugs sowie des versuchten Betrugs Bundesrecht verletzt (<ref-ruling> E. 8.2 mit Hinweisen).
2. Die Beschwerde ist gutzuheissen. Das Bundesgericht kann einen Entscheid, der den Anforderungen von <ref-law> nicht genügt, an die kantonale Behörde zur Verbesserung zurückweisen oder aufheben (<ref-law>; zum früheren Recht <ref-ruling> E. 2.6). Das Urteil des Obergerichts des Kantons Zürich vom 24. März 2011 ist somit zur Verbesserung und neuen Entscheidung an die Vorinstanz zurückzuweisen.
Der Beschwerdeführerin ist keine Entschädigung zuzusprechen (<ref-law>). Der Beschwerdegegner unterliegt mit seinem Antrag, die Beschwerde sei abzuweisen, weshalb ihm die Kosten des Verfahrens aufzuerlegen sind. Er stellt indes ein Gesuch um unentgeltliche Rechtspflege, das gutzuheissen ist, da seine Bedürftigkeit ausgewiesen scheint (<ref-law>). Dem Rechtsvertreter des Beschwerdegegners, Lucius Richard Blattner, ist eine angemessene Entschädigung aus der Bundesgerichtskasse auszurichten.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Das angefochtene Urteil des Obergerichts des Kantons Zürich vom 24. März 2011 wird aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege des Beschwerdegegners wird gutgeheissen.
3. Es werden keine Gerichtskosten erhoben.
4. Dem Rechtsvertreter des Beschwerdegegners, Lucius Richard Blattner, wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 3'000.-- ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 24. November 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Keller