Sachverhalt: A. Y._ (geb. 1956) ist Staatsangehöriger von Bosnien und Herzegowina und hielt sich seit Januar 1983 bis August 2004 zusammen mit seiner Ehefrau ununterbrochen in der Schweiz auf. Er verfügte zunächst über eine Aufenthalts- und seit 1993 über eine Niederlassungsbewilligung. Im August 2004 meldete sich Y._ bei der Fremdenpolizei (heute: Einwohnerdienste, Migration und Fremdenpolizei) der Einwohnergemeinde Bern definitiv in seine Heimat - wo er ein Haus besitzt - ab, worauf seine Niederlassungsbewilligung erlosch. Gleichzeitig erwirkte er bei seiner Pensionskasse die Barauszahlung der Austrittsleistung. Im Dezember 2004 reiste Y._ mit einem Touristenvisum erneut in die Schweiz ein und hält sich seither bei seiner Ehefrau X._ (geb. 1951) auf. Diese ist ebenfalls bosnisch-herzegowinische Staatsangehörige und verfügt seit 1979 über eine Niederlassungsbewilligung. Das Ehepaar hat zwei Töchter (geb. 1982 und 1984). Y._ hat zudem aus einer früheren Ehe einen Sohn und eine Tochter (geb. 1979 und 1982); der Sohn reiste 1991 im Rahmen des Familiennachzugs in die Schweiz ein. B. X._ reichte am 10. Juni 2005 bei der Einwohnergemeinde Bern ein Gesuch um Nachzug ihres Ehemannes ein. Mit Verfügung vom 23. November 2006 wurde das Gesuch abgewiesen und Y._ eine Ausreisefrist bis 15. Januar 2007 gesetzt. Die Einwohnergemeinde Bern machte geltend, der Anspruch auf Erteilung einer Aufenthaltsbewilligung erlösche, wenn ein Ausweisungsgrund vorliege. Die Familie X._ und Y._ werde sozialhilferechtlich unterstützt und es lägen Verlustscheine in der Höhe von über Fr. 160'000.-- vor. Zudem sei Y._ gerichtlich verurteilt worden. C. Gegen diesen Entscheid erhob X._ Beschwerde an die Polizei- und Militärdirektion des Kantons Bern, welche mit Entscheid vom 26. Juni 2007 die Beschwerde als unbegründet abwies. Gleichzeitig legte die Polizei- und Militärdirektion die Ausreisefrist für Y._ neu auf den 10. August 2007 fest. Eine gegen diesen Entscheid erhobene Beschwerde wies das Verwaltungsgericht des Kantons Bern, das Y._ ebenfalls als Partei in das Verfahren einbezog, mit Urteil vom 13. Oktober 2008 ab und setzte diesem eine neue Ausreisefrist bis 5. Dezember 2008. D. Mit Eingabe vom 11. November 2008 erheben X._ und Y._ gegen das Urteil des Verwaltungsgerichts beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie beantragen, der angefochtene Entscheid sei aufzuheben und es sei Y._ die Aufenthaltsbewilligung im Rahmen des Familiennachzugs zu gewähren; eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Sodann ersuchen sie um die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. E. Das Verwaltungsgericht sowie die Polizei- und Militärdirektion des Kantons Bern, die Einwohnergemeinde Bern und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.