Sachverhalt:
A. Das Bezirksgericht Zürich verurteilte X._ am 1. März 2010 wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz unter Anrechnung der erstandenen Haft sowie des vorzeitigen Strafvollzugs von insgesamt 683 Tagen zu einer Freiheitsstrafe von vier Jahren. Zugleich ordnete es die Rückversetzung in den Vollzug der gemäss Verfügung des Justizvollzugs des Kantons Zürich vom 7. November 2006 noch ausstehenden Reststrafe von 65 Tagen an und widerrief die mit Urteil des Bezirksamtes Bremgarten vom 8. September 2004 bedingt ausgefällte Gefängnisstrafe von 60 Tagen. Zurzeit befindet sich X._ in der Strafanstalt Pöschwies. Zwei Drittel der Strafe waren am 25. Januar 2011 verbüsst. Reguläres Strafende ist der 15. Juni 2012.
B. X._ ersuchte am 13. Dezember 2010 um die bedingte Entlassung aus dem Strafvollzug auf den 25. Januar 2011. Mit Verfügung vom 17. Januar 2011 wiesen die Bewährungs- und Vollzugsdienste des Amtes für Justizvollzug des Kantons Zürich das Gesuch ab. Gegen diese Verfügung erhob Rechtsanwalt Dr. Y._ am 14. Februar 2011 im Namen von X._ Rekurs bei der Direktion der Justiz und des Innern. Diese setzte dem Rechtsvertreter mit Schreiben vom 15. Februar 2011 eine Frist von zehn Tagen an, um eine Vollmacht von X._ nachzureichen, ansonsten auf den Rekurs nicht eingetreten werde. Die Frist lief am 28. Februar 2011 unbenützt ab, weshalb mit Verfügung vom 4. März 2011 auf den Rekurs nicht eingetreten wurde.
C. Rechtsanwalt Dr. Y._ reichte mit Eingabe vom 11. April 2011 Beschwerde beim Verwaltungsgericht des Kantons Zürich ein. Dieses setzte mit Verfügung vom 15. April 2011 Rechtsanwalt Dr. Y._ bzw. X._ eine Frist von zehn Tagen an, um eine schriftliche Vollmacht nachzureichen, ansonsten auf die Beschwerde nicht eingetreten werde. In der Folge reichte Rechtsanwalt Dr. Y._ eine von X._ am 24. April 2011 unterzeichnete Vollmacht betreffend "Verfügung vom 17. Januar 2011" ein. Am 27. April 2011 ging beim Verwaltungsgericht zudem eine von X._ am 22. April 2011 unterzeichnete und in englischer Sprache verfasste Vollmacht betreffend "Release of Custody" ein. Das Verwaltungsgericht wies die Beschwerde mit Urteil vom 13. Mai 2011 ab.
D. Rechtsanwalt Dr. Y._ erhebt in seinem sowie im Namen von X._ Beschwerde in Strafsachen an das Bundesgericht. Er beantragt, das Urteil des Verwaltungsgerichts vom 13. Mai 2011 sei aufzuheben und die Sache zur materiellen Beurteilung der Rechtsfrage zurückzuweisen. Zudem sei ihnen die unentgeltliche Rechtspflege zu gewähren. Eventualiter sei zumindest von der Erhebung eines Kostenvorschusses abzusehen.
Mit Schreiben vom 4. Juli 2011 wurde Rechtsanwalt Dr. Y._ aufgefordert, die fehlende Vollmacht von X._ für das bundesgerichtliche Verfahren bis am 16. August 2011 bzw. nach Fristerstreckungsgesuch bis am 16. September 2011 nachzureichen, ansonsten die Rechtsschrift unbeachtet bleibe. Am 22. August 2011 ging die Vollmacht von X._ beim Bundesgericht ein.

Erwägungen:
1. Die Vorinstanz auferlegte dem Beschwerdeführer 2 einen Teil der Gerichtskosten, weshalb er über ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids im Sinne von <ref-law> verfügt. Er ist somit zur Beschwerde berechtigt.
2. Soweit sich die Beschwerdeführer zur materiellen Rechtsfrage der bedingten Entlassung äussern (Beschwerde, S. 3 ff.), ist nicht auf die Beschwerde einzutreten. Gegenstand des vorliegenden Verfahrens bildet einzig der angefochtene Entscheid. Dieser befasst sich ausschliesslich mit der Frage, ob die Direktion der Justiz und des Innern zu Recht nicht auf den vom Beschwerdeführer 2 im Namen des Beschwerdeführers 1 erhobenen Rekurs eingetreten ist.
3. 3.1 Die Beschwerdeführer machen geltend, die Vorinstanz habe den Nichteintretensentscheid der Direktion der Justiz und des Innern zu Unrecht gutgeheissen. Es verstosse gegen das Verbot des überspitzten Formalismus, dass aufgrund der fehlenden Vollmacht die materielle Rechtsfrage der bedingten Entlassung nicht behandelt worden sei (Beschwerde, S. 3). Der Beschwerdeführer 1 habe die Verfügung vom 17. Januar 2011 dem Beschwerdeführer 2 zugesandt. Damit habe ab diesem Zeitpunkt zwischen den beiden ein privatrechtliches Vertretungsverhältnis bestanden (Beschwerde, S. 5). Gestützt auf die Rechtsweggarantie nach <ref-law> müsse dem Beschwerdeführer 1 als mittelloser und der deutschen Sprache unkundiger Ausländer das Recht gewährt werden, sich gegen einen ihn belastenden Entscheid zur Wehr zu setzen (Beschwerde, S. 4).
3.2 Die Vorinstanz erwägt mit Verweis auf die kantonale Rechtsprechung zum Verwaltungsrechtspflegegesetz des Kantons Zürich, bei fehlender schriftlicher Vollmacht könne sich eine Bevollmächtigung auch stillschweigend aus den Umständen ergeben. Dies sei indessen vorliegend nicht der Fall. Der Beschwerdeführer 2 könne alleine daraus, dass ihm der Beschwerdeführer 1 einen Entscheid der Vollzugsbehörde zukommen liess, nicht ohne weiteres auf eine Mandatierung schliessen. Vielmehr hätte er sich nach Massgabe der ihm zukommenden anwaltlichen Sorgfaltspflicht beim Beschwerdeführer 1 über das weitere Vorgehen informieren und instruieren lassen müssen, nur schon, um dem Sprachunkundigen den Inhalt der Verfügung zu erläutern. Obwohl er über genügend Zeit verfügt habe, habe er dies unterlassen. Zudem habe der Beschwerdeführer 1 den Kostenvorschuss, den der Beschwerdeführer 2 von ihm verlangt habe, nicht geleistet. Dies spreche ebenfalls nicht für das Vorliegen eines auftragsrechtlichen Verhältnisses (vorinstanzliches Urteil, E. 4.2).
3.2 Die Vorinstanz erwägt mit Verweis auf die kantonale Rechtsprechung zum Verwaltungsrechtspflegegesetz des Kantons Zürich, bei fehlender schriftlicher Vollmacht könne sich eine Bevollmächtigung auch stillschweigend aus den Umständen ergeben. Dies sei indessen vorliegend nicht der Fall. Der Beschwerdeführer 2 könne alleine daraus, dass ihm der Beschwerdeführer 1 einen Entscheid der Vollzugsbehörde zukommen liess, nicht ohne weiteres auf eine Mandatierung schliessen. Vielmehr hätte er sich nach Massgabe der ihm zukommenden anwaltlichen Sorgfaltspflicht beim Beschwerdeführer 1 über das weitere Vorgehen informieren und instruieren lassen müssen, nur schon, um dem Sprachunkundigen den Inhalt der Verfügung zu erläutern. Obwohl er über genügend Zeit verfügt habe, habe er dies unterlassen. Zudem habe der Beschwerdeführer 1 den Kostenvorschuss, den der Beschwerdeführer 2 von ihm verlangt habe, nicht geleistet. Dies spreche ebenfalls nicht für das Vorliegen eines auftragsrechtlichen Verhältnisses (vorinstanzliches Urteil, E. 4.2).
3.3 3.3.1 Wird die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung) gerügt, gelten qualifizierte Anforderungen an die Begründung. Eine solche Rüge prüft das Bundesgericht nicht von Amtes wegen, sondern nur, wenn sie in der Beschwerde vorgebracht und substanziiert begründet worden ist. Das bedeutet, dass klar und detailliert anhand der Erwägungen des angefochtenen Entscheids darzulegen ist, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-law>; <ref-ruling> E. 1.4.1 mit Hinweisen).
3.3.2 Die Beschwerdeführer setzen sich weitgehend nicht mit den vorinstanzlichen Erwägungen auseinander. Die Vorinstanz befasst sich ausführlich mit der Rüge der Verletzung der Rechtsweggarantie nach <ref-law>, worauf in Anwendung von <ref-law> verwiesen werden kann (vorinstanzliches Urteil, E. 4.4).
Der vorinstanzlichen Schlussfolgerung, es seien keine Umstände ersichtlich, aufgrund welcher sich zwischen den Beschwerdeführern stillschweigend ein Mandatsverhältnis ergebe, vermögen diese nichts Entscheidendes entgegenzusetzen. Mit dem Einwand, der Beschwerdeführer 1 habe dem Beschwerdeführer 2 die massgebliche Verfügung zukommen lassen, was ein Auftragsverhältnis belege, hat sich die Vorinstanz ausführlich auseinandergesetzt. Sie legt dar, weshalb dies nicht genügt, um von einem Mandatsverhältnis auszugehen. Mit diesen Ausführungen befassen sich die Beschwerdeführer nicht.
Auf die Beschwerde ist in diesen Punkten nicht einzutreten.
3.3.3 Das aus <ref-law> fliessende Verbot des überspitzten Formalismus wendet sich gegen prozessuale Formenstrenge. Überspitzter Formalismus als besondere Form der Rechtsverweigerung ist gegeben, wenn für ein Verfahren rigorose Formvorschriften aufgestellt werden, ohne dass die Strenge sachlich gerechtfertigt wäre, wenn die Behörde formelle Vorschriften mit übertriebener Schärfe handhabt oder an Rechtsschriften überspannte Anforderungen stellt und damit dem Bürger den Rechtsweg in unzulässiger Weise versperrt (<ref-ruling> E. 2.1 mit Hinweisen).
Der vorinstanzliche Entscheid, den Nichteintretensentscheid der Direktion der Justiz und des Innern gutzuheissen, verletzt das Verbot des überspitzten Formalismus nicht. Dem Beschwerdeführer 2 war es möglich und zumutbar, die Vollmacht des Beschwerdeführers 1 rechtzeitig einzuholen. Überdies wurde ihm eine Nachfrist angesetzt, um den Mangel der fehlenden Vollmacht zu beheben. Seine Vorbringen hierzu sind gänzlich unbehelflich. So macht er geltend, das Einbringen einer Vollmacht habe eine Besprechung mit dem Beschwerdeführer 1 erfordert. Ein Besuch in der Strafanstalt Pöschwies sei mit grösserem Aufwand sowie entsprechender Planung verbunden, was ihm nicht sogleich möglich gewesen sei. Zudem sei es schwierig gewesen, den Beschwerdeführer 1 davon zu überzeugen, das Dokument zu unterzeichnen (Beschwerde, S. 5).
Angesichts dieser Umstände ist die Rüge der Beschwerdeführer unbegründet und die Beschwerde in diesem Punkt abzuweisen.
4. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Das Gesuch um unentgeltliche Rechtspflege ist ebenfalls abzuweisen, da die Beschwerde von vornherein aussichtslos war (<ref-law>). Bei diesem Ausgang des Verfahrens sind die bundesgerichtlichen Kosten den Beschwerdeführern je zur Hälfte aufzuerlegen. Der finanziellen Lage des Beschwerdeführers 1 ist bei der Bemessung der Gerichtsgebühr 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. 3.1 Dem Beschwerdeführer 1 werden Gerichtskosten von Fr. 500.-- auferlegt.
3.2 Dem Beschwerdeführer 2 werden Gerichtskosten von Fr. 1'000.-- auferlegt.
4. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 27. September 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Horber