Sachverhalt:
A. Das Bezirksgericht Zürich verurteilte X._ am 6. Juli 2010 wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz (aArt. 19 Ziff. 1 Abs. 4 und 5 BetmG in Verbindung mit aArt. 19 Ziff. 2 lit. a BetmG; Anklageziffern 1.2, 1.3, 1.6, 2.1 und 2.2) zu einer Freiheitsstrafe von 3 1⁄2 Jahren, unter Anrechnung von 509 Tagen Untersuchungs- und Sicherheitshaft. Ausserdem widerrief es die vom Bezirksgericht Zürich am 12. Juli 2006 ausgefällte bedingte Gefängnisstrafe von fünf Monaten und die vom Tribunal de police de Genève am 10. November 2006 ausgesprochene bedingte Gefängnisstrafe von acht Monaten, unter Anrechnung von 158 Tagen erstandener Haft. Das Bezirksgericht sprach X._ von den Vorwürfen der Widerhandlung gegen das Betäubungsmittelgesetz gemäss Anklageziffern 1.1, 1.4, 1.5 und 2.2 frei.
B. Auf Berufung von X._ hin verurteilte ihn das Obergericht des Kantons Zürich am 4. April 2011 wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz (aArt. 19 Ziff. 1 Abs. 4-6 BetmG in Verbindung mit aArt. 19 Ziff. 2 lit. a BetmG; Anklageziffern 1.6, 2.1 und 2.2) zu einer Freiheitsstrafe von 39 Monaten, unter Anrechnung von 781 Tagen Untersuchungs- und Sicherheitshaft. Ausserdem widerrief es die erwähnten bedingt ausgesprochenen früheren Gefängnisstrafen. Das Obergericht sprach X._ von den Vorwürfen der Widerhandlung gegen das Betäubungsmittelgesetz gemäss Anklageziffern 1.1-1.5 frei.
C. Das Obergericht sieht es als erwiesen an, dass X._ (zusammen mit A._) am 26. September 2008 mit seinem Fahrzeug einen unbekannten bulgarischen Drogenkurier von Zürich nach Adliswil lotste, wo unter anderem A._ im Auftrag von X._ eine unbekannte Menge Heroin, mindestens jedoch 250-300 Gramm, aus der Autobatterie des Fahrzeugs mit bulgarischen Kennzeichen ausbaute und an den Empfänger in Adliswil übergab (Anklagepunkt 1.6).
Weiter übergab X._ Ende Januar 2009 B._ an dessen Wohnort in Adliswil zwei Blöcke Heroin zu ca. 500 Gramm und in Zürich ein Säcklein mit ca. 50 Gramm Kokain. B._ übergab die Drogen auf Anweisung von X._ an C._ in dessen Wohnung. Dafür erhielt er Fr. 3'000.-- oder Fr. 3'500.--, die er X._ aushändigte (Anklagepunkt 2.1).
Schliesslich übergab X._ am 10. Februar 2009 B._ in Adliswil zwei Blöcke Heroin zu ca. 500 Gramm, der diese auf Anweisung von X._ vorerst in seiner Wohnung in Adliswil zwischenlagern und einen der Blöcke am Folgetag in Zürich abliefern sollte, wo er verhaftet wurde (Anklagepunkt 2.2).
D. X._ erhebt Beschwerde in Strafsachen. Er beantragt, das Urteil des Obergerichts des Kantons Zürich vom 4. April 2011 sei aufzuheben, und er sei vom Vorwurf der qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz (aArt. 19 Ziff. 1 Abs. 4-6 BetmG in Verbindung mit aArt. 19 Ziff. 2 lit. a BetmG Anklageziffern 1.6, 2.1 und 2.2) freizusprechen und angemessen zu entschädigen. Eventualiter sei das Urteil des Obergerichts aufzuheben und die Sache zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen. X._ beantragt ausserdem die unentgeltliche Rechtspflege und Verbeiständung.
E. Das Obergericht des Kantons Zürich verzichtet auf eine Vernehmlassung. Die Staatsanwaltschaft des Kantons Zürich beantragt sinngemäss Abweisung der Beschwerde. Der Beschwerdeführer reichte zusätzliche Gegenbemerkungen ein.

Erwägungen:
1. 1.1 Der Beschwerdeführer rügt im Zusammenhang mit der Anklageziffer 1.6 eine unrichtige Feststellung des Sachverhalts, die Verletzung der Grundsätze des fairen Verfahrens (Art. 6 Ziff. 1 EMRK), "in dubio pro reo" (<ref-law> und Art. 6 Ziff. 2 EMRK) und Willkür (<ref-law>, Beschwerde, S. 4 ff.). Die vorinstanzliche Sachverhaltsfeststellung stütze sich auf die Antwort von A._, obwohl diese auf eine suggestive Frage des einvernehmenden Polizeibeamten erfolgt sei. Zudem sei dieser während mehrerer Tage mit B._, der ihn (den Beschwerdeführer) mit seinen Aussagen ebenfalls belaste, in der gleichen Zelle eingesperrt gewesen. Die Sachverhaltsfeststellung sei aus diesen Gründen unrichtig und dürfe nicht gegen ihn verwertet werden (Beschwerde, S. 4 f.). Im Übrigen bestünden bei einer objektiven Würdigung der Aussagen von A._ erhebliche und unüberwindbare Zweifel, ob er (der Beschwerdeführer) tatsächlich A._ zusammen mit dem bulgarischen Drogenkurier zurück nach Adliswil gelotst habe. Eine korrekte Würdigung der Aussagen hätte ergeben, dass jener der Lotse nach Adliswil gewesen sei (Beschwerde, S. 6 f.). Es sei inkonsequent, dass das Obergericht die Aussagen von A._ hinsichtlich der Anklageziffern 1.1-1.5 als nicht glaubhaft bewerte, jedoch bei der Anklageziffer 1.6 gerade darauf abstelle und den Schuldspruch damit begründe. A._ habe ein Motiv, ihn zu Unrecht zu belasten, habe er doch ausgesagt, dass er ihn verabscheue (Beschwerde, S. 8).
Schliesslich verfalle die Vorinstanz in Willkür, indem sie ihm unterstelle, er habe gewusst, dass es sich bei der Fahrt von Zürich nach Adliswil um eine Drogenfahrt gehandelt habe. Er habe dies konstant bestritten. Zumindest bestünden bei dieser unklaren Sachlage "in dubio pro reo" erhebliche und unüberwindbare Zweifel an seinem Vorsatz (Beschwerde, S. 10).
1.2 Die Vorinstanz gibt ausführlich die relevanten Aussagen der Tatbeteiligten wieder (angefochtenes Urteil, S. 25 ff.). Obwohl A._ anfänglich in untauglicher Weise versucht habe, den Beschwerdeführer nicht zu belasten, habe er den Kern des Tatgeschehens immer gleich, lebendig, detailreich und schlüssig geschildert. Es könnten keine vernünftigen Zweifel bestehen, dass sich die Geschehnisse so abgespielt hätten, wie dies A._ ausgeführt habe. Er habe den Beschwerdeführer dabei keineswegs übermässig belastet, was gegen die These spreche, A._ und B._ hätten sich in der Zelle abgesprochen. Die Aussage des Beschwerdeführers, er habe nicht gewusst, dass es um einen Drogentransport gehe, stelle eine unbehelfliche Schutzbehauptung dar (angefochtenes Urteil, S. 27 ff.).
1.3 Dem Sachgericht steht im Bereich der Beweiswürdigung ein erheblicher Ermessensspielraum zu (<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; zum Begriff der Willkür <ref-ruling> E. 2.4 mit Hinweisen). Inwiefern das kantonale Gericht sein Ermessen missbraucht haben soll, ist in der Beschwerde klar und detailliert aufzuzeigen (<ref-ruling> E. 1.3). Auf ungenügend begründete Rügen und bloss allgemein gehaltene appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling> E. 2.2 mit Hinweis).
1.4 Der Beschwerdeführer vermag keine Willkür an der vorinstanzlichen Sachverhaltsfeststellung darzutun. Er zeigt nicht auf, und es ist auch nicht ersichtlich, inwiefern die Vorinstanz ihr Ermessen missbraucht hätte, indem sie die Stellung des Beschwerdeführers als Lotse eines bulgarischen Drogenkuriers von Zürich nach Adliswil bejahte. Die Rügen des Beschwerdeführers, wie etwa der beanstandete Umstand, dass A._ und B._ zeitweilig in einer Zelle eingesperrt waren, sind appellatorisch und können die sorgfältigen vorinstanzlichen Erwägungen nicht in Frage stellen. Darauf ist nicht einzutreten.
2. 2.1 Der Beschwerdeführer erachtet in Bezug auf die Anklageziffer 2 des angefochtenen Urteils das Bundesgesetz vom 20. Juni 2003 über die verdeckte Ermittlung (BVE, AS 2004, S. 1409 und den seitherigen Änderungen) als verletzt. Es habe keine gültige richterliche Genehmigung in Bezug auf die verdeckte polizeiliche Ermittlung vorgelegen, die zur Verhaftung von ihm und B._ geführt habe. Die vorinstanzlich erwähnte Genehmigung befinde sich nicht in den Verfahrensakten (Beschwerde, S. 11 ff.).
C._ und der Polizeibeamte, der als verdeckter Ermittler fungiert habe, hätten zudem unzulässig auf seine Willensbildung eingewirkt, indem sie diesem aktiv SMS gesendet und ihn aufgefordert hätten, 500 Gramm Heroin zu liefern, was ebenfalls gegen das BVE verstosse (Beschwerde, S. 15).
2.2 Die Vorinstanz erwägt, es habe sich beim ermittelnden Polizeibeamten um einen ordnungsgemäss ernannten verdeckten Ermittler gehandelt. Diesem sei es erlaubt gewesen, einen bereits vorhandenen Tatentschluss zu konkretisieren. Der Polizeibeamte und C._ hätten darüber hinaus nichts getan, vielmehr habe der Beschwerdeführer per SMS C._ die nächste Lieferung nahezu aufgedrängt, ihm zumindest aber ein konkretes Angebot gemacht, das er nur noch habe annehmen müssen (angefochtenes Urteil, S. 33 f.).
2.3 Verfahrenshandlungen, die vor der am 1. Januar 2011 in Kraft getretenen Schweizerischen Strafprozessordnung vom 5. Oktober 2007 (Strafprozessordnung, StPO, SR 312.0) angeordnet oder durchgeführt worden sind, behalten ihre Gültigkeit (<ref-law>). Für die Beurteilung der Zulässigkeit der verdeckten Ermittlung ist daher im vorliegenden Fall das BVE anwendbar.
2.4 Der Beschwerdeführer beanstandet zu Unrecht eine angeblich fehlende richterliche Genehmigung der verdeckten Ermittlung. Die erforderliche Genehmigung wurde von der Präsidentin der Anklagekammer des Obergerichts des Kantons Zürich am 12. November 2008 erteilt, nachdem der verdeckte Ermittler durch das Kommando der Kantonspolizei Zürich mit Verfügung vom 10. November 2008 ernannt worden war (Vernehmlassung Oberstaatsanwaltschaft Zürich, act. 11, S. 2). Die Vorinstanz hat zwar in ihrem Entscheid nicht ausdrücklich auf die entsprechenden Dokumente hingewiesen. Dies ändert jedoch nichts, dass im fraglichen Zeitpunkt eine richterliche Genehmigung der verdeckten Ermittlung vorlag. Die nachträglichen Vorbringen des Beschwerdeführers in seinen Gegenbemerkungen zur Vernehmlassung sind unbehelflich (act. 14, S. 2).
2.5 Nach der bundesgerichtlichen Rechtsprechung kann der Einsatz eines verdeckten Ermittlers, der als eigentlicher "agent provocateur" oder "Lockspitzel" auftritt, dazu führen, dass die provozierte Person straflos bleibt. Durch die Anstiftung wird bei einem anderen der Entschluss zu einer bestimmten rechtswidrigen Tat hervorgerufen (<ref-ruling> E. 2c mit Hinweisen). Der Tatentschluss muss auf das motivierende Verhalten des Anstifters zurückzuführen sein und bedarf insofern eines Kausalzusammenhangs. Nicht erforderlich ist, dass beim Anzustiftenden Widerstände zu überwinden wären. Auch bei demjenigen, der bereits zur Tat geneigt ist oder sich zur Begehung von Straftaten sogar anbietet, kann ein Tatentschluss noch hervorgerufen werden, und zwar solange, als er zur konkreten Tat nicht entschlossen ist (BGE a.a.O.). Ein solcher Fall liegt nicht vor. Der Beschwerdeführer hatte gemäss Vorinstanz bereits vor dem Auftreten des verdeckten Ermittlers die Absicht, Heroin und Kokain an C._ zu liefern, was er ihm per SMS vom 6. Februar 2009 auch mitgeteilt hat. Der Schuldspruch ist nicht zu beanstanden.
3. 3.1 Der Beschwerdeführer macht im Sinne eines Eventualbegehrens geltend, dass die Vorinstanz in Bezug auf die Anklageziffern 2.1 und 2.2 den Grundsatz "in dubio pro reo" verletzt und eine willkürliche Beweiswürdigung vorgenommen habe (Beschwerde, S. 15 ff.).
3.2 Die Vorinstanz erachtet die für die Anklageziffern 2.1 und 2.2 zentralen Aussagen von B._ als glaubhaft. Seine Aussagen zeichneten sich durch grosse Konstanz aus, ohne gelernt zu wirken. Gewisse Ungereimtheiten stellten kein Indiz für die Unglaubhaftigkeit der gesamten Aussage dar. Die Erzählungen seien offen, lebendig und nachvollziehbar. Der Beschwerdeführer mache demgegenüber unglaubhafte und abenteuerliche Schutzbehauptungen (angefochtenes Urteil, S. 29 ff.).
3.3 Die Vorbringen des Beschwerdeführers zu den Anklageziffern 2.1 und 2.2 sind unbehelflich. Sie zeigen keine willkürliche Sachverhaltsfeststellung der Vorinstanz auf. Deren Ausführungen sind vielmehr ausführlich begründet und nachvollziehbar. Die vom Beschwerdeführer angeführten angeblichen Ungereimtheiten, wie etwa in den Aussagen von B._, können hieran nichts ändern. Auf seine appellatorische Kritik am vorinstanzlichen Urteil ist nicht einzutreten.
4. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Sein Gesuch um Gewährung der unentgeltlichen Rechtspflege ist abzuweisen, da die Beschwerde von vornherein aussichtslos war. Seiner finanziellen Lage ist mit herabgesetzten 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 Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 21. Mai 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Keller