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. 