Sachverhalt: A. A.X._ (geb. 1980), Staatsangehöriger von Bosnien und Herzegowina, reiste am 22. Dezember 1998 in die Schweiz ein und stellte gleichentags ein Asylgesuch, welches mit Verfügung des Bundesamtes für Flüchtlinge (heute Bundesamt für Migration) am 14. September 1999 abgewiesen wurde. Am 20. Juli 2001 heiratete er die aus Serbien stammende, in der Schweiz niedergelassene B._, die am 27. November 2001 das Schweizer Bürgerrecht erhielt. Seit Mai 2006 ist A.X._ im Besitz einer Niederlassungsbewilligung. Am 11. Dezember 2006 kam die gemeinsame Tochter der Eheleute X._ zur Welt. B. A.X._ ist in der Schweiz mehrfach straffällig geworden. Er wurde wie folgt verurteilt: Am 4. Februar 2002 wegen Widerhandlungen gegen das Strassenverkehrsgesetz zu zehn Tagen Gefängnis, bedingt vollziehbar bei einer Probezeit von zwei Jahren, und einer Busse von Fr. 700.--. Am 24. Mai 2002 wegen erneuter Widerhandlungen gegen das Strassenverkehrsgesetz zu zehn Tagen Haft, bedingt vollziehbar bei einer Probezeit von einem Jahr, und einer Busse von Fr. 400.--. Am 25. November 2005 (vom Kreisgericht XI Interlaken-Oberhasli) bzw. am 28. Juni 2006 (vom Obergericht des Kantons Bern als Berufungsinstanz) wegen Vergewaltigung, mehrfacher sexueller Nötigung, Gewalt und Drohung gegen Behörden und Beamte sowie wegen mehrfacher Verletzung des Strassenverkehrsgesetzes durch vorsätzliches Vereiteln einer angeordneten Blutprobe sowie Führens eines Personenwagens ohne gültigen Führerausweis zu 24 Monaten Zuchthaus und einer unbedingt zu vollziehenden Landesverweisung von drei Jahren. A.X._ trat den Strafvollzug am 7. September 2006 an. Am 7. September 2007 wurde er unter das Regime der Vollzugsprogressionsstufe "Electronic Monitoring (Backdoor Variante)" versetzt. Zwei Drittel der Strafe waren am 6. Januar 2008 verbüsst. C. Das Amt für Migration und Personenstand des Kantons Bern (Migrationsdienst) verfügte am 22. Juni 2007 die Ausweisung von A.X._ auf unbestimmte Dauer und ordnete an, er habe die Schweiz nach Verbüssung seiner Strafe zu verlassen. Eine von A.X._ gegen diese Verfügung erhobene Beschwerde wies die Polizei- und Militärdirektion des Kantons Bern mit Entscheid vom 14. November 2007 ab. Das Verwaltungsgericht des Kantons Bern schützte am 2. Juni 2008 den abschlägigen Entscheid der Polizei- und Militärdirektion. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 4. Juli 2008 beantragen A._ und B.X._, den Entscheid des Verwaltungsgerichtes des Kantons Bern vom 2. Juni 2008 aufzuheben. Es sei dem Beschwerdeführer die Ausweisung lediglich anzudrohen und ihm die Niederlassungsbewilligung zu "verlängern" (recte: zu belassen). Das Verwaltungsgericht des Kantons Bern beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Polizei- und Militärdirektion des Kantons Bern und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Amt für Migration und Personenstand des Kantons Bern hat auf Vernehmlassung verzichtet. E. Am 9. Juli 2008 hat der Abteilungspräsident der Beschwerde - antragsgemäss - aufschiebende Wirkung zuerkannt. 