Sachverhalt: A. Der albanische Staatsangehörige X._ (geb. 30. August 1977) reiste Ende 1999/Anfang 2000 illegal in die Schweiz ein. Am 6. Juni 2000 wurde er wegen Verdachts auf Heroinhandel verhaftet und befand sich in der Folge in Untersuchungshaft bzw. im vorzeitigen Strafvollzug. Mit Urteil des Bezirksgerichts Uster vom 18. September 2001 wurde er der Widerhandlung gegen das Bundesgesetz über Aufenthalt und Niederlassung der Ausländer sowie der mehrfachen Widerhandlung gegen das Betäubungsmittelgesetz schuldig gesprochen und mit drei Jahren Zuchthaus bestraft. Mit Verfügung vom 27. Mai 2002 verhängte das Bundesamt für Ausländerfragen (heute: Bundesamt für Migration) über ihn eine Einreisesperre auf unbestimmte Dauer. Nach Verbüssung von zwei Dritteln der Strafe wurde X._ am 5. Juni 2002 nach Albanien ausgeschafft. Ende 2003 lernte X._ in Konstanz seine heutige Ehefrau, die Schweizer Bürgerin Y._ (geb. 1973) kennen. Aus dieser Beziehung ging am 10. Dezember 2004 der Sohn Z._ hervor. Am 10. August 2005 wurde X._ in Winterthur verhaftet und mit Strafbefehl der Staatsanwaltschaft Winterthur/Unterland vom 11. August 2005 des Vergehens gegen das Bundesgesetz über Aufenthalt und Niederlassung der Ausländer sowie des Diebstahls schuldig gesprochen und mit drei Monaten Gefängnis unbedingt bestraft. Am 14. August 2005 wurde er erneut nach Albanien ausgeschafft. B. Am 1. November 2005 liess sich Y._ von ihrem früheren aus dem Kosovo stammenden Ehemann scheiden. Mit Verfügung vom 24. März 2006 wies das Migrationsamt des Kantons Zürich das Gesuch von X._ um Bewilligung der Einreise zur Vorbereitung der Heirat mit Y._ ab. Am 19. Mai 2006 fand die Heirat in Albanien statt. Die Ehe und die Geburt des gemeinsamen Kindes wurden am 14. Mai 2007 im Zivilstandsregister von E._/SZ eingetragen. C. Am 25. Mai 2006 und am 30. August 2007 ersuchte X._ bei der Schweizer Vertretung in Tirana (Albanien) um Bewilligung der Einreise zum Verbleib bei der Ehefrau im Kanton Zürich. Die Sicherheitsdirektion (Migrationsamt) des Kantons Zürich wies die Gesuche mit Verfügung vom 30. Januar 2008 im Wesentlichen mit der Begründung ab, X._ habe wiederholt zu schweren Klagen Anlass gegeben. Dagegen rekurrierte X._ ohne Erfolg an den Regierungsrat des Kantons Zürich. Die Beschwerde gegen den Regierungsratsbeschluss wies das Verwaltungsgericht des Kantons Zürich mit Entscheid vom 1. April 2009 ab. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 5. Mai 2009 beantragen X._, Y._ sowie das gemeinsame Kind Z._, den Entscheid des Verwaltungsgerichts vom 1. April 2009 aufzuheben und die Aufenthaltsbewilligung zu erteilen, eventualiter die Sache im Sinne der Erwägungen zur Neubeurteilung zurückzuweisen. Zudem ersuchen sie um unentgeltliche Rechtspflege. Das Verwaltungsgericht des Kantons Zürich hat auf Vernehmlassung verzichtet. Die Staatskanzlei des Kantons Zürich - im Auftrag des Regierungsrates und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.