Sachverhalt: A. X._, geb. 3. März 1991, stammt nach eigenen Angaben aus Bangladesch. Er reiste am 25. Juli 2002 zusammen mit seiner Mutter und seinem Bruder illegal in die Schweiz ein und stellte am Folgetag ein Asylgesuch. Das Bundesamt für Migration (BFM) lehnte dieses am 3. Mai 2004 ab und wies sowohl X._ als auch dessen Mutter und Bruder aus der Schweiz weg. Es setzte ihnen für die Ausreise aus der Schweiz Frist bis zum 28. Juni 2004. Die gegen diese Verfügung erhobenen Rechtsmittel blieben erfolglos. X._ hat die Schweiz bis heute nicht verlassen. Am 13. Oktober 2008 wurde X._ vom Migrationsdienst des Kantons Bern in Ausschaffungshaft genommen. Mit Entscheid vom 15. Oktober 2008 bestätigte das Haftgericht III Bern-Mittelland die Anordnung der Ausschaffungshaft für die Zeit bis zum 12. Januar 2009. B. Gegen den Entscheid des Haftgerichts III Bern-Mittelland führt X._ mit Eingabe vom 29. Oktober 2008 Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt, es sei der angefochtene Entscheid aufzuheben und er sei aus der Ausschaffungshaft zu entlassen. Am 17. November 2008 reichte der Beschwerdeführer eine ergänzende Eingabe ein. Das Haftgericht III Bern-Mittelland und der Migrationsdienst des Kantons Bern schliessen auf Abweisung der Beschwerde. Das BFM verzichtet in seiner Vernehmlassung auf einen Antrag.