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.

Erwägungen:
1. 1.1 <ref-law> schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
1.2 Das streitige Gesuch um Erteilung der Aufenthaltsbewilligung wurde vor Inkrafttreten des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) am 1. Januar 2008 eingereicht und beurteilt sich daher noch nach dem inzwischen aufgehobenen Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG) und seinen Ausführungserlassen (Art. 126 Abs. 1 AuG).
1.3 Der Beschwerdeführer 1 ist mit einer Schweizer Bürgerin verheiratet. Er hat damit nach Art. 7 ANAG einen grundsätzlichen Anspruch auf Erteilung einer Aufenthaltsbewilligung. Ein analoger Anspruch besteht zudem aufgrund des in Art. 8 EMRK bzw. <ref-law> garantierten Rechts auf Achtung des Familienlebens, da die familiären Beziehungen zur Ehegattin sowie zum gemeinsamen Kind - soweit ersichtlich - intakt sind und den Umständen entsprechend tatsächlich gelebt werden (vgl. <ref-ruling> E. 3.1 S. 285 f.; <ref-ruling> E. 5.3.1 S. 211, je mit Hinweisen). Ob der Anspruch erloschen ist, weil - wie die Vorinstanzen angenommen haben - ein Ausweisungsgrund nach Art. 10 Abs. 1 ANAG vorliegt, ist eine Frage der materiellen Beurteilung und nicht der Zulässigkeit des Rechtsmittels (<ref-ruling> E. 1.1.5 S. 149 f.). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten erweist sich damit als zulässig (<ref-law>).
Allein der Beschwerdeführer 1 ist Adressat des angefochtenen Entscheids. Ob die Beschwerdeführer 2 und 3, die schon am Verfahren vor den kantonalen Behörden hätten teilnehmen können, unter diesen Umständen zur Beschwerde an das Bundesgericht berechtigt sind (vgl. <ref-law>), kann jedoch dahin gestellt bleiben, da auf die Beschwerde des Beschwerdeführers 1 jedenfalls einzutreten ist und das Rechtsmittel ohnehin nicht durchdringt.
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
1.5 Gemäss <ref-law> hat die Rechtsschrift die Begehren und deren Begründung zu enthalten. In der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Die Vorbringen müssen sachbezogen sein, damit aus der Beschwerdeschrift ersichtlich ist, in welchen Punkten und weshalb der angefochtene Entscheid beanstandet wird. Dies setzt voraus, dass sich ein Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzt (<ref-ruling>). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.2 S. 254). Eine diesen Anforderungen (Art. 42 Abs. 2 bzw. <ref-law>) genügende Begründung ist vorliegend nur teilweise zu erkennen. Soweit eine solche fehlt, kann auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht eingetreten werden.
2. 2.1 Gemäss Art. 7 Abs. 1 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers - wie erwähnt - grundsätzlich Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung (erster Satz). Der Anspruch erlischt, wenn ein Ausweisungsgrund vorliegt (dritter Satz).
2.2 Der Ausländer kann aus der Schweiz unter anderem ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde (Art. 10 Abs. 1 lit. a ANAG). Die Ausweisung soll aber nur verfügt werden, wenn sie nach den gesamten Umständen "angemessen", d.h. verhältnismässig, erscheint (Art. 11 Abs. 3 ANAG). Hierbei sind vor allem die Schwere des Verschuldens des Ausländers, die Dauer seiner Anwesenheit in der Schweiz und die ihm und seiner Familie drohenden Nachteile zu berücksichtigen (Art. 16 Abs. 3 der Vollziehungsverordnung vom 1. März 1949 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer). Eine vergleichbare Interessenabwägung setzt im Übrigen gemäss Art. 8 Ziff. 2 EMRK auch ein Eingriff in das Recht auf Achtung des Familienlebens voraus (<ref-ruling> E. 4.1 S. 22 f.). Ein solcher ist statthaft, falls er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung oder zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesundheit und Moral sowie der Rechte und Freiheiten anderer notwendig erscheint.
Ob die Ausweisung gemäss den massgeblichen Bestimmungen verhältnismässig ist, ist eine Rechtsfrage, die vom Bundesgericht im vorliegenden Beschwerdeverfahren frei geprüft wird. Dem Bundesgericht ist es jedoch verwehrt, sein eigenes Ermessen - im Sinne einer Überprüfung der Zweckmässigkeit der Ausweisung - an die Stelle des Ermessens der zuständigen kantonalen Behörde zu setzen (BGE <ref-ruling> E. 5.1 S. 208 mit Hinweis).
3. 3.1 Der Beschwerdeführer wurde in der Schweiz zu einer Zuchthausstrafe von drei Jahren sowie zu einer Gefängnisstrafe von 3 Monaten verurteilt. Damit liegt ein Ausweisungsgrund nach Art. 10 Abs. 1 lit. a ANAG vor. Zu prüfen bleibt, ob sich die Ausweisung bzw. die Verweigerung des Familiennachzugs als verhältnismässig erweist.
3. 3.1 Der Beschwerdeführer wurde in der Schweiz zu einer Zuchthausstrafe von drei Jahren sowie zu einer Gefängnisstrafe von 3 Monaten verurteilt. Damit liegt ein Ausweisungsgrund nach Art. 10 Abs. 1 lit. a ANAG vor. Zu prüfen bleibt, ob sich die Ausweisung bzw. die Verweigerung des Familiennachzugs als verhältnismässig erweist.
3.2 3.2.1 Ausgangspunkt und Massstab für die Schwere des Verschuldens und die fremdenpolizeiliche Interessenabwägung ist die vom Strafrichter verhängte Strafe (<ref-ruling> E. 3.1 S. 216). Der selber nicht drogensüchtige Beschwerdeführer hat mit einer Menge von Heroin gehandelt, die als schwerer Fall qualifiziert wurde. Die Verurteilung zu einer Freiheitsstrafe von drei Jahren wegen Betäubungsmitteldelikten deutet auf ein erhebliches Verschulden hin und lässt auf eine ausgeprägte Geringschätzung und Gleichgültigkeit gegenüber der schweizerischen Rechtsordnung schliessen. Dieser Eindruck wird durch die Tatsache verstärkt, dass der Beschwerdeführer trotz Verurteilung und Einreisesperre im Jahr 2005 erneut illegal in die Schweiz eingereist ist und zudem während seines illegalen Aufenthalts einen Diebstahl begangen hat. Entgegen den Behauptungen der Beschwerdeführer erscheint auch die Prognose hinsichtlich eines zukünftigen Wohlverhaltens als ungewiss. Selbst wenn die Drogendelikte schon einige Jahre zurück liegen, besteht somit nach wie vor ein ein erhebliches öffentliches Interesse, den Beschwerdeführer von der Schweiz fernzuhalten.
3.2.2 Den öffentlichen Interessen sind im Rahmen der Verhältnismässigkeitsprüfung die privaten Interessen des Beschwerdeführers und seiner Angehörigen an einem gemeinsamen Aufenthalt in der Schweiz gegenüberzustellen: Der Beschwerdeführer hat sich noch nie ordnungsgemäss in der Schweiz aufgehalten, weshalb ihn die verfügte fremdenpolizeiliche Fernhaltemassnahme nicht übermässig treffen wird. Zwar mag es sein, dass dem Beschwerdeführer in Albanien nicht die gleichen wirtschaftlichen Perspektiven offen stehen wie in der Schweiz. Diese Folge ist jedoch einzig seinem kriminellen Verhalten zuzuschreiben und deshalb hinzunehmen.
Die Ehegattin und der gemeinsame Sohn, der im Übrigen noch in einem anpassungsfähigen Alter ist, sind Schweizer Bürger. Sie haben bisher nicht in Familiengemeinschaft mit dem Beschwerdeführer 1 gelebt. In Albanien haben sie sich bis anhin nur ferienhalber aufgehalten. Die Beschwerdeführerin 2 geht in der Schweiz einer Arbeit nach, auf die sie nicht verzichten möchte, und ist hier selbstverständlich sozial und gesellschaftlich verwurzelt. Bereits als sie den Beschwerdeführer 1 kennen lernte, wusste sie indessen, dass diesem nicht gestattet war, in die Schweiz einzureisen wegen Verstosses gegen das Betäubungsmittelgesetz, wobei er ihr aber angeblich nicht alles gesagt habe. Der Beschwerdeführerin 2 war allerdings aufgrund ihrer Erfahrungen mit ihrem damaligen Ehemann, der ebenfalls wegen Drogendelikten verurteilt worden war, die Problematik der straffälligen Ausländer nicht völlig fremd, was sie zur genaueren Abklärung der Vergangenheit des Beschwerdeführers hätte veranlassen sollen. Spätestens als der Beschwerdeführer am 14. August 2005 (erneut) ausgeschafft und ihm am 24. März 2006 die Einreise in die Schweiz zur Vorbereitung der Heirat verweigert wurde, hat der Beschwerdeführerin jedoch bewusst sein müssen, dass sie nicht davon ausgehen konnte, die eheliche Gemeinschaft mit dem Beschwerdeführer 1 in der Schweiz leben zu können.
Zu berücksichtigen ist ferner, dass bei einem mit einem Schweizer Bürger verheirateten Ausländer, der erstmals oder nach bloss kurzer Aufenthaltsdauer um die Erneuerung seiner Bewilligung ersucht, das Bundesgericht annimmt, dass die Grenze, von der an in der Regel selbst dann keine solche mehr erteilt wird, wenn dem Ehepartner die Ausreise un- oder nur schwer zumutbar erscheint, bei einer Freiheitsstrafe von zwei Jahren liegt. In dieser Situation bedarf es praxisgemäss aussergewöhnlicher Umstände, um die Erteilung einer Aufenthaltsbewilligung dennoch zu rechtfertigen ("Reneja"-Praxis: <ref-ruling> ff.), auch wenn es sich bei der Zweijahresregel um keine feste Grenze handelt, die im Einzelfall nicht über- oder unterschritten werden dürfte. Ob der Beschwerdeführerin die Übersiedlung in das Heimatland des Beschwerdeführers - sollte sie sich dazu entscheiden - zumutbar wäre, kann unter diesen Umständen dahingestellt bleiben, umso mehr als der Beschwerdeführer 1 zu einer Freiheitsstrafe verurteilt wurde, die klar über dem Richtwert von zwei Jahren liegt.
3.3 Aufgrund des Gesagten überwiegt das öffentliche Interesse an der Fernhaltung des Beschwerdeführers dessen private und familiäre Interessen an einem Aufenthalt in der Schweiz. Der Beschwerdeführer hat durch seine schweren strafrechtlichen Verfehlungen den Anspruch auf eine Aufenthaltsbewilligung gemäss Art. 7 ANAG verwirkt. Entsprechendes gilt auch für das aus Art. 8 EMRK ableitbare Aufenthaltsrecht. Von einer Verletzung von Art. 3 EMRK sowie <ref-law> kann nicht die Rede sein, wobei es diesbezüglich ohnehin an einer genügenden Begründung (E. 1.5) mangelt. Wenn das Verwaltungsgericht vorliegend die Voraussetzungen für die Verweigerung des Familiennachzugs als erfüllt erachtete, verstiess es damit weder gegen Bundesrecht noch gegen staatsvertragliche Verpflichtungen. Weitere Ausführungen erübrigen sich; ergänzend kann auf die Erwägungen im angefochtenen Entscheid sowie im Regierungsratsbeschluss vom 5. November 2008 verwiesen werden (<ref-law>).
4. 4.1 Die Beschwerde erweist sich somit als offensichtlich unbegründet und ist im vereinfachten Verfahren nach <ref-law> abzuweisen, soweit darauf eingetreten werden kann.
4.2 Die Beschwerdeführer ersuchen um unentgeltliche Rechtspflege. Nach <ref-law> wird diese gewährt bei Bedürftigkeit, sofern die Rechtsbegehren nicht aussichtslos erscheinen. Vorliegend kann dem Gesuch schon wegen Aussichtslosigkeit des Beschwerdebegehrens nicht entsprochen werden. Zudem ist die angebliche Bedürftigkeit in keiner Weise belegt. Die Kosten des bundesgerichtlichen Verfahrens sind somit den Beschwerdeführern 1 und 2 unter Solidarhaft aufzuerlegen (Art. 65 und Art. 66 Abs. 1 und 5 BGG). Eine Parteientschädigung ist nicht auszurichten (<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. 2'000.-- werden den Beschwerdeführern 1 und 2 unter Solidarhaft auferlegt.
4. Dieses Urteil wird den Beschwerdeführern, der Sicherheitsdirektion, dem Regierungsrat und dem Verwaltungsgericht (4. Kammer) des Kantons Zürich sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 18. November 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Müller Dubs