Faits:
A. Le 3 août 2002, X._, ressortissant camerounais né en 1975, a déposé une demande d'asile qui a été rejetée par l'Office fédéral des réfugiés (actuellement et ci-après: l'Office fédéral des migrations) le 3 décembre 2002. X._ n'a pas quitté la Suisse, malgré un délai échéant le 28 janvier 2003 pour ce faire, et ne s'est notamment pas présenté à l'aéroport le 28 janvier 2007 pour prendre le vol de retour dans son pays d'origine. Il a ensuite disparu.
B. Le 20 mai 2008, X._ a déposé une demande d'autorisation de séjour au motif qu'il souhaitait se marier avec Y._, ressortissante suisse née en 1963. Par décision du 9 juin 2008, invoquant l'exclusivité de la procédure d'asile, le Service de la population du canton de Vaud (ci-après: le Service de la population) a refusé la demande d'autorisation de séjour puisque l'intéressé n'était pas au bénéfice d'une admission provisoire, qu'il faisait l'objet d'une décision de renvoi et que, n'étant pas marié, il n'avait pas droit à une autorisation de séjour. X._ et Y._ ont recouru contre cette décision.
Le 25 juin 2008, les intéressés ont demandé à l'Office de l'état civil l'ouverture de la procédure préparatoire de mariage.
C. Le 30 juin 2008, X._ a été interpellé sur réquisition du Service de la population. Le même jour, le Juge de paix du district de Lausanne a ordonné la mise en détention administrative de l'intéressé. Par arrêt du 22 juillet 2008, le Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) a rejeté le recours de X._ à l'encontre de cette ordonnance du 30 juin 2008. Le Tribunal fédéral a fait de même par arrêt du 1er septembre 2008.
D. Le 4 septembre 2008, le Tribunal cantonal a rejeté le recours de X._ et Y._ et a maintenu la décision du 9 juin 2008 du Service de la population. Il a retenu que X._ ne pouvait pas se prévaloir d'un droit à une autorisation de séjour en vertu de l'art. 8 CEDH. Il ne vivait, en effet, avec Y._ que depuis le mois de janvier 2008 et il ne pouvait pas invoquer un mariage sérieusement voulu et imminent puisque la date du mariage n'avait pas pu être fixée, la procédure préparatoire n'ayant débutée que le 25 juin 2008. Dès lors, au vu de l'exclusivité de la procédure d'asile, il ne pouvait pas présenter une demande de regroupement familial.
E. Agissant par la voie du recours en matière de droit public, X._ et Y._ demandent au Tribunal fédéral, principalement, d'annuler l'arrêt du 4 septembre 2008 et de dire que X._ est autorisé à résider dans le canton de Vaud et à y exercer une activité, par octroi d'une autorisation de séjour ou de renvoyer la cause au Tribunal cantonal pour ce faire ou encore que le Tribunal cantonal renvoie à son tour la cause au Service de la population; subsidiairement, de dire que X._ est autorisé à résider dans le canton de Vaud et à y exercer une activité lucrative jusqu'à son mariage avec Y._, par octroi d'une autorisation de séjour ou de renvoyer la cause au Tribunal cantonal pour ce faire ou encore que le Tribunal cantonal renvoie à son tour la cause au Service de la population. Ils invoquent essentiellement la violation de l'art. 8 CEDH.
Le Service de la population renonce à déposer des observations et se réfère à l'arrêt attaqué. Le Tribunal cantonal et l'Office fédéral des migrations concluent au rejet du recours dans le mesure où il est recevable.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 444; <ref-ruling> cons. 1 p. 521 et les arrêts cités).
2. L'objet de la présente procédure ne porte pas sur l'octroi de l'autorisation de séjour en tant que telle, mais uniquement sur l'existence d'un éventuel droit pour le recourant à obtenir celle-ci au titre du regroupement familial, ce qui lui permettrait d'en faire la demande sans devoir quitter la Suisse comme le prévoit l'<ref-law> (arrêt 2C_551/2008 du 17 novembre 2008 consid. 3.2).
Or, il ressort du recours des intéressés devant le Tribunal fédéral que X._ a été refoulé au Cameroun le 2 septembre 2008. Il s'agit d'un fait nouveau dont le Tribunal de céans peut toutefois tenir compte puisque, lorsqu'il examine la question de la recevabilité d'un recours, le Tribunal fédéral se fonde sur la situation réelle existant au moment où le recours est déposé (cf. <ref-law>; Bernard Corboz, Introduction à la nouvelle loi sur le Tribunal fédéral, SJ II 319 ss p. 345). On peut dès lors se demander si la présente procédure n'est pas devenue sans objet. En effet, que l'intéressé ait ou non un droit à obtenir une autorisation de séjour, il ne pourra pas présenter sa demande depuis la Suisse puisqu'il n'y est plus. Le recours devant de toute façon être déclaré irrecevable, cette question peut rester ouverte.
3. Selon l'<ref-law>, a qualité pour former un recours de droit public quiconque est, notamment, particulièrement atteint par la décision ou l'acte normatif attaqué (let. b) et a un intérêt digne de protection à son annulation ou à sa modification (let. c).
On peut douter du fait que Y._ possède la qualité pour recourir. En effet, n'est pas en cause l'octroi de l'autorisation de séjour elle-même - et dans un tel cas, la concubine, contrairement à l'épouse suisse ayant pris part à la procédure cantonale aux côtés de son conjoint, ne possède pas forcément la qualité pour recourir (cf. arrêt 2C_408/2007 du 5 décembre 2007 consid. 2.2 et les arrêts cités) - mais uniquement le droit de déposer une demande de regroupement familial sans quitter la Suisse. L'intéressée est ainsi touchée par l'arrêt attaqué mais uniquement de manière indirecte. La question peut néanmoins également rester indécise, le recours étant de toute façon irrecevable pour d'autres motifs.
4. 4.1 Selon l'art. 83 lettre c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Par ailleurs, l'art. 14 al. 1 de la loi fédérale du 26 juin 1998 sur l'asile (LAsi; RS 142.31) prévoit qu'un requérant débouté ne peut engager une procédure visant à l'octroi d'une autorisation de séjour avant d'avoir quitté la Suisse, à moins qu'il n'y ait droit.
En l'espèce, l'arrêt attaqué retient que le recourant n'a pas de droit à obtenir une autorisation de séjour sur la base de l'art. 8 CEDH et que, partant, il ne peut mener une procédure tendant à l'octroi d'une telle autorisation avant d'avoir quitté la Suisse en application de l'art. 14 al. LAsi. Dans un tel cas, le point de savoir si le recourant dispose d'un droit à une autorisation de séjour est à la fois une condition de la recevabilité du recours en matière de droit public (art. 83 let. c ch. 2 LTF) et une question relevant du fond, qui touche à l'application de l'<ref-law>. Conformément à la jurisprudence, cette question doit être examinée dans le cadre de la recevabilité (<ref-ruling> consid. 1 p. 283 s.), étant précisé que, sous cet angle, il suffit que le recourant rende vraisemblable que les conditions fondant la compétence du tribunal sont remplies, le point de savoir si tel est effectivement le cas étant ensuite tranché, pour autant que les autres conditions de recevabilité soient réunies, avec l'examen de la cause au fond (arrêt 2C_484/2008 du 9 janvier 2009 destiné à la publication consid. 1.3).
4.2 Au vu de l'objet de la présente procédure (cf. consid. 2), la conclusion tendant à l'octroi d'une autorisation, prise dans le recours, est irrecevable.
5. 5.1 En principe, l'étranger n'a pas droit à l'autorisation de séjour, à moins que ne puisse être invoquée une disposition particulière du droit fédéral ou d'un traité accordant le droit à la délivrance d'une telle autorisation (<ref-ruling> consid. 1 p. 342).
Un étranger peut toutefois, selon les circonstances, se prévaloir de l'art. 8 § 1 CEDH pour s'opposer à l'éventuelle séparation de sa famille et obtenir ainsi une autorisation de séjour. Encore faut-il, pour pouvoir invoquer cette disposition, que la relation entre l'étranger et une personne de sa famille ayant le droit de résider durablement en Suisse soit étroite et effective (<ref-ruling> consid. 3.1 p. 285; <ref-ruling> consid. 5.3.1 p. 211). D'après la jurisprudence, les relations familiales qui peuvent fonder, en vertu de cette disposition, un droit à une autorisation de police des étrangers sont avant tout les rapports entre époux ainsi qu'entre parents et enfants mineurs vivant ensemble (<ref-ruling> consid. 1d p. 261). Les fiancés ou les concubins ne sont en principe pas habilités à invoquer l'art. 8 CEDH; ainsi, l'étranger fiancé à une personne ayant le droit de s'établir en Suisse ne peut, en règle générale, pas prétendre à une autorisation de séjour, à moins que le couple n'entretienne depuis longtemps des relations étroites et effectivement vécues et qu'il n'existe des indices concrets d'un mariage sérieusement voulu et imminent - comme, par exemple, la publication des bans du mariage tel qu'exigée avant la modification du code civil suisse du 26 juin 1998 - (cf. arrêts 2C_300/2008 du 17 juin 2008 consid. 4.2, 2C_90/2007 du 27 août 2007 consid. 4.1, 2A.362/2002 du 4 octobre 2002 consid. 2.2).
Comme susmentionné, dans le cadre de l'<ref-law>, une demande d'autorisation de séjour fondée uniquement sur l'art. 8 CEDH ne peut être introduite qu'après le renvoi de l'étranger concerné. Une exception au principe de l'exclusivité de la procédure d'asile n'est admise que si le droit à l'autorisation de séjour requise est manifeste (arrêt 2A.673/2006 du 18 décembre 2006 consid. 3.3).
5.2 En l'espèce, les recourants ont habité ensemble de janvier à août 2008. Comme l'autorité intimée l'a retenu à bon droit, une cohabitation de six mois n'est pas suffisamment longue pour que X._ puisse bénéficier du droit au regroupement familial tiré de l'art. 8 CEDH. En outre, les recourants ne peuvent pas invoquer un mariage imminent puisque, comme déjà dit, X._ a été refoulé au Cameroun le 2 septembre 2008. Ainsi, la date du mariage est aléatoire puisqu'elle dépend de la possibilité donnée à Y._ de se rendre au Cameroun pour pouvoir s'y marier, l'Office des migrations ayant rendu une décision le 12 novembre 2008 d'interdiction d'entrée sur la territoire suisse d'une durée de trois ans à l'encontre de X._.
Dans ces circonstances, le droit à l'autorisation de séjour n'est pas manifeste et les recourants, dans une argumentation confuse, ne rendent pas vraisemblable que tel serait le cas. Dès lors, X._ ne peut pas tirer de l'art. 8 CEDH un droit à une autorisation de séjour qui ferait obstacle à l'application de l'<ref-law>. Il appartiendra à l'intéressé de présenter sa demande de regroupement familial depuis l'étranger en temps voulu. Partant, le présent recours est irrecevable.
6. Succombant, les recourants doivent supporter un émolument judiciaire solidairement entre eux (<ref-law>) et n'ont pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. Un émolument judiciaire de 1'500 fr. est mis à la charge des recourants solidairement entre eux.
3. Le présent arrêt est communiqué au mandataire des recourants, au Service de la population et à la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 12 mars 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
R. Müller E. Kurtoglu-Jolidon