Faits:
A. A.a Originaire du Cameroun, X._, né le *** 1979 (alias Y._, né le *** 1987) a déposé une demande d'asile en Suisse le 8 novembre 2006, qui a été définitivement rejetée le 12 mars 2007, un délai lui étant imparti au 13 avril 2007 pour quitter la Suisse.
Le 24 août 2011, il est devenu père de jumeaux et sa reconnaissance de paternité a été inscrite dans les registres de l'état civil.
A.b Entre 2007 et 2011, X._ a fait l'objet en Suisse des condamnations pénales suivantes :
- le 27 mars 2007, à cinq jours-amende de 480 fr. pour infraction à la LStup;
- le 11 juin 2009, à quarante jours-amende pour faux dans les certificats, contravention à la législation sur le séjour et l'établissement des étrangers, séjour illégal, activité lucrative sans autorisation et contravention à la LStup;
- le 23 février 2010, à 24 mois de privation de liberté assortie d'un sursis partiel et d'une amende de 500 fr. pour faux dans les certificats, blanchiment d'argent, infraction grave et contravention à la LStup ainsi que séjour illégal;
- le 16 septembre 2011, à 20 jours de privation de liberté pour séjour illégal.
A.c Parallèlement à ces condamnations, X._ a été le destinataire de différentes décisions et démarches de la part des autorités administratives :
- le 24 avril 2007, le Service de la population du canton de Vaud (ci-après: le Service cantonal) lui a réservé un vol de départ prévu le 15 mai 2007; l'intéressé a refusé de signer le plan de vol, ne s'est pas présenté à l'aéroport et n'a plus donné signe de vie;
- arrêté le 16 août 2007, X._ a été placé en détention administrative jusqu'au 12 octobre 2007;
- le 3 mars 2010, X._ a été refoulé par vol spécial à destination du Cameroun, mais il est revenu en Suisse quelques jours plus tard;
- le 18 janvier 2011, il a fait l'objet d'une décision d'interdiction d'entrée en Suisse pour une durée indéterminée;
- le 21 mars 2011, le Service cantonal, faisant suite à une requête de l'intéressé alléguant des projets de mariage, a déclaré que son séjour n'était pas légal;
- le 20 mai 2011, le Service cantonal a prononcé le renvoi de Suisse de X._, lui fixant un délai de départ au 19 juin 2011;
- le 13 janvier 2012, le Service cantonal a refusé de lui délivrer une autorisation de séjour en raison notamment de ses condamnations pénales et a prononcé son renvoi de Suisse.
B. Entre le 13 octobre 2011 et le 16 février 2012, X._ a été placé en détention administrative pour une durée de 6 mois, durant laquelle il a signé, le 4 novembre 2011, une déclaration de retour volontaire au Cameroun.
Le 16 février 2012, la détention administrative de l'intéressé a été levée par le Service cantonal, pour qu'il puisse purger une peine de détention pénale jusqu'au 7 mars 2012.
Le 6 mars 2012, un jour avant que X._ finisse de purger sa peine privative de liberté, le Service cantonal a requis du Juge de paix le placement en détention administrative de l'intéressé, afin de préparer son retour dans son pays d'origine.
Par ordonnance du Juge de paix du 7 mars 2012, X._ a été placé en détention administrative. Ce magistrat a transmis le dossier à la Présidente du Tribunal cantonal pour qu'elle désigne un avocat d'office à l'intéressé.
A la suite d'une requête de l'Office fédéral des migrations (ci-après: l'Office fédéral) du 13 mars 2012, l'Ambassade du Cameroun a fixé une audition de l'intéressé au 18 avril 2012.
Le recours formé par X._ à l'encontre de l'ordonnance du 7 mars 2012 a été rejeté et la décision attaquée confirmée par arrêt du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) du 17 avril 2012.
C. A l'encontre de l'arrêt du Tribunal cantonal du 17 avril 2012, X._ forme un recours en matière de droit public au Tribunal fédéral. Il conclut principalement à la réforme de l'arrêt attaqué, à l'admission de son recours, à ce que l'ordonnance de mise en détention du 7 mars 2012 soit déclarée nulle, respectivement annulée et à ce qu'il soit immédiatement libéré. Subsidiairement, il demande l'annulation de l'arrêt attaqué et le renvoi de la cause au Tribunal cantonal pour instruction complémentaire et nouvelle décision dans le sens des considérants. Il requiert par ailleurs l'assistance judiciaire.
Par ordonnance présidentielle du 29 mai 2012, le Tribunal fédéral a rejeté la requête de mise en liberté immédiate formée à titre provisionnel par X._.
Le Service cantonal a produit son dossier, mais il a renoncé à se déterminer, à l'instar du Tribunal cantonal. L'Office fédéral n'a pas pris position. X._ a déclaré s'en remettre à son mémoire de recours, tout en soulignant qu'aucune démarche en vue de l'exécution du renvoi n'avait été entreprise depuis deux mois.

Considérant en droit:
1. 1.1 En matière de mesures de contrainte, le recours en matière de droit public est en principe ouvert (<ref-law>; arrêts 2C_10/2009 du 5 février 2009 consid. 2, non publié aux <ref-ruling>; 2C_478/2012 du 14 juin 2012 consid. 1.1).
Dirigé contre un arrêt final, émanant d'une autorité judiciaire cantonale supérieure de dernière instance (cf. art. 86 al. 1 let. d et al. 2 LTF), le présent recours a été formé en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par le recourant, qui, se trouvant en détention administrative pour une durée de six mois, a indéniablement qualité pour agir (<ref-law>). Il convient donc d'entrer en matière.
1.2 Dans la mesure où le recourant dirige ses conclusions à l'encontre de l'ordonnance du 7 mars 2012, son recours n'est pas recevable, en raison de l'effet dévolutif complet des actes déposés auprès du Tribunal cantonal (<ref-ruling> consid. 1.2 p. 104; cf. art. 31 al. 1 et 2 de la loi du 18 décembre 2007 d'application dans le Canton de Vaud de la législation fédérale sur les étranger; LVLEtr/VD; RS/VD 142.11). En revanche, lorsque le recourant reproche aux juges cantonaux de n'avoir pas reconnu la nullité de la mise en détention du 8 mars 2012 et, subsidiairement, de ne pas l'avoir annulée, ses griefs sont recevables.
2. Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'<ref-law>. Il y procède en se fondant sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 7.4 p. 230; <ref-ruling> consid. 4.3 p. 62) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. <ref-law>), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées. Sinon, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué. Aucun fait nouveau ni preuve nouvelle ne peut être présenté, à moins de résulter de la décision de l'autorité précédente (<ref-law>).
L'application de ces principes empêche de prendre en compte la version des événements figurant dans le recours qui s'écarte des constatations cantonales. En effet, le recourant se contente de présenter une argumentation appellatoire, sans alléguer ni a fortiori démontrer que les faits figurant dans l'arrêt attaqué seraient manifestement inexacts ou arbitraires, ce qui n'est pas admissible (<ref-ruling> consid. 5.2.2 p. 322).
3. Invoquant une violation des articles 79 LEtr, 9 et 10 Cst., ainsi que 5 CEDH, le recourant soutient à titre principal que son maintien en détention ne repose sur aucune décision valable. Selon lui, la mise en détention du 8 mars 2012 était nulle, puisqu'au moment où elle a été prononcée, il était encore sous le coup de la décision de détention rendue le 14 octobre 2011. En effet, contrairement à ce qui a été constaté par le Tribunal cantonal, aucun élément de preuve ne permettait de retenir que l'autorité compétente aurait levé sa détention au sens de l'art. 22 al. 2 ch. 1 LVLEtr/VD le 16 février 2012, au moment de sa mise en détention pénale. Comme la détention de six mois ordonnée le 14 octobre 2011 s'était terminée le 13 avril 2012, il était donc incarcéré illégalement depuis lors.
3.1 L'argumentation du recourant part de la prémisse que c'est à tort que l'arrêt attaqué retient que la détention prononcée le 14 octobre 2011 a été levée le 16 février 2012 au sens de l'art. 22 al. 2 ch. 1 LVEtr/VD. Cette contestation relève des faits et de l'interprétation du droit cantonal, que le Tribunal fédéral ne revoit que sous l'angle de l'arbitraire (cf. <ref-ruling> consid. 3 p. 351 s.). On peut dès lors se demander si la motivation présentée à son appui est suffisante (cf. <ref-law>; supra consid. 2). La question peut demeurer indécise, dès lors que le grief est de toute façon infondé.
3.2 Il découle de l'art. 22 al. 2 LVLEtr/VD que le Service cantonal a la compétence d'ordonner la levée de la détention administrative lorsque les conditions ne sont plus remplies ou lorsque le renvoi de la personne détenue peut être exécuté (ch. 1); il peut aussi désigner l'établissement de détention et ordonner le cas échéant le transfert dans un autre établissement (ch. 3). Le texte de cette disposition n'impose pas l'établissement d'une décision écrite et le recourant ne soutient du reste pas que tel serait le cas. Si un document écrit est évidemment souhaitable, son absence ne suffit donc pas à qualifier de manifestement inexacte ou arbitraire l'affirmation du Tribunal cantonal selon laquelle une telle levée de détention a été prononcée. Encore faut-il qu'il existe des indices suffisants en ce sens. Tel n'est pas le cas en l'espèce. En effet, il est admis que le recourant a été transféré, le 16 février 2012, du centre de détention administrative de A._ (GE) à la prison de B._ (VD) pour y être détenu pénalement. Or, ce transfert ne constitue pas qu'un simple changement de lieu de détention tel que visé à l'art. 22 al. 2 ch. 3 LVLEtr/VD, mais il implique aussi un titre de détention différent et n'a pu être effectué qu'en accord avec les autorités compétentes, après que la détention administrative a été levée pour faire place à la détention pénale. Il en découle que l'on ne peut reprocher au Tribunal cantonal d'avoir retenu que la détention administrative du recourant avait été levée le 16 février 2012.
3.3 Au demeurant, l'argumentation du recourant perd de vue qu'en vertu de l'art. 80 al. 6 let. c LEtr, la détention est levée lorsque la personne détenue doit subir une peine ou une mesure privative de liberté; en d'autres termes, la détention administrative cède le pas à la détention pénale et prend en principe automatiquement fin à partir du moment auquel l'étranger commence à purger sa peine privative pénale (cf. arrêts 2A.348/2002 du 18 juillet 2002 consid. 2.3; 2A.507/1997 du 25 novembre 1997 consid. 2b/bb; ANDREAS ZÜND, ad art. 80 LEtr, in: Migrationsrecht [Marc Spescha et al. (éd.)], 3e éd., Zurich 2012, p. 224 N 10; cf. aussi THOMAS HUGI YAR, Zwangsmassnahmen im Ausländerrecht, in: Ausländerrecht [Peter Uebersax et al. (éd.)], 2e éd., Bâle 2009, p. 475 s. N 10.109 s.).
3.4 Ces constatations font perdre toute portée au grief du recourant. En effet, elles excluent qu'il y ait eu chevauchement entre la mise en détention prononcée le 13 octobre 2011 qui a cessé de produire ses effets dès sa levée le 16 février 2012 et la mise en détention litigieuse du 7 mars 2012. Cette dernière ne peut donc être qualifiée de nulle ni annulée pour ce motif, de sorte que le grief selon lequel, à partir du 13 avril 2012, le maintien du recourant en détention ne reposerait sur aucun titre valable et serait contraire aux art. 79 LEtr, 9 et 10 Cst., ainsi que 5 CEDH doit être rejeté.
Au surplus, les griefs que le recourant soulève au sujet de la détention pénale subie (déduction de la durée de la détention administrative de celle de la peine privative de liberté, principe ne bis in idem), laquelle ne fait pas l'objet de la présente procédure, sont irrecevables (cf. arrêt 2C_206/2009 du 29 avril 2009 consid. 2 et 5.1.2).
4. A titre subsidiaire, le recourant se plaint d'une violation des art. 76 et 80 LEtr, ainsi que 5 et 8 CEDH.
4.1 Il conteste tout d'abord que les conditions de mise en détention de l'art. 76 al. 1 let. b ch. 1, 3 et 4 LEtr soient remplies.
Selon la jurisprudence, les motifs de l'art. 76 al. 1 let. b ch. 3 et 4 LEtr sont réalisés en particulier lorsque l'étranger tente d'entraver les démarches en vue de l'exécution du renvoi en donnant des indications manifestement inexactes ou contradictoires ou encore s'il laisse clairement apparaître, par ses déclarations ou son comportement, qu'il n'est pas disposé à retourner dans son pays d'origine (cf. <ref-ruling> consid. 3.1 p. 58 s.; arrêts 2C_413/2012 du 22 mai 2012 consid. 3.2; 2C_963/2010 du 11 janvier 2011 consid. 2.1). Comme le prévoit expressément l'art. 76 al. 1 let. b ch. 3 LEtr, il faut qu'il existe des éléments concrets en ce sens (arrêts 2C_478/2012 du 14 juin 2012 consid. 2.2; 2C_413/2012 du 22 mai 2012 consid. 3.2 in fine; 2C_675/2011 du 20 septembre 2011 consid. 2.1).
En l'espèce, le recourant conteste en vain les indices retenus dans l'ordonnance du Juge de paix, alors que seule la position figurant dans l'arrêt attaqué est pertinente. Comme les juges cantonaux l'ont retenu, les faits constatés dénotent que le recourant a fait l'objet de plusieurs décisions de renvoi et qu'il s'est toujours soustrait à son départ. En 2007 déjà, un vol avait été réservé pour lui; il ne s'était pas présenté et n'avait plus donné signe de vie. En 2010, il a été refoulé par vol spécial, mais il est aussitôt revenu en Suisse. Ces éléments constituent des indices concrets suffisant à justifier la mise en détention du recourant au sens de l'art. 76 al. 1 let. b ch. 3 et 4 LEtr. Le fait qu'en février 2011, le recourant se soit par ailleurs adressé au Service cantonal pour déposer une demande d'autorisation de séjour en vue de son mariage, qu'il se soit déplacé pour qu'une décision puisse lui être notifiée le 20 mai 2011 et qu'il n'ait plus été convoqué jusqu'à son arrestation le 13 octobre 2011 n'est pas suffisant pour faire perdre toute portée aux indices concrets précités.
Dès lors que les conditions de l'art. 76 al. 1 let. b ch. 3 et 4 LEtr sont remplies, la mise en détention administrative du recourant est justifiée, sans qu'il ne soit au surplus nécessaire d'examiner si les condamnations pénales infligées constitueraient de surcroît un motif suffisant au sens de l'art. 76 al. 1 let. b ch. 1 LEtr.
4.2 Le recourant fait grief au Tribunal cantonal de ne pas avoir, sous l'angle de l'examen de la proportionnalité imposé par l'art. 80 al. 4 LEtr et de l'art. 5 de la directive 2008/115/CE du Parlement européen et du Conseil du 16 décembre 2008 relative aux normes et procédures communes applicables dans les Etats membres au retour des ressortissants de pays tiers en séjour irrégulier (ci-après: la directive sur le renvoi, en vigueur pour la Suisse dès le 1er janvier 2011 [RO 2010 p. 5925]), tenu compte du fait qu'il était père de deux enfants et qu'il avait l'intention d'épouser leur mère.
La détention dans son ensemble doit rester proportionnée (arrêt 2C_304/2012 du 1er mai 2012 consid. 1). L'art. 80 al. 4 LEtr prescrit au juge de la détention de prendre notamment en considération la situation familiale de la personne détenue. Cette prescription correspond à l'exigence de l'art. 5 de la directive sur le renvoi, qui impose aux Etats membres de tenir notamment compte de la vie familiale lorsqu'ils mettent en oeuvre ladite directive. Il n'appartient toutefois pas au juge de la détention de se substituer au juge du renvoi et d'examiner si la situation familiale du recourant empêche son éloignement, car la décision de renvoi ne fait pas l'objet de la procédure de détention. Selon la pratique, le juge de la détention ne peut refuser d'approuver la mise en détention en vue du renvoi que lorsque la décision de renvoi apparaît comme manifestement infondée (<ref-ruling> consid. 2 p. 58; <ref-ruling> consid. 2.2.2 p. 198; arrêt 2C_304/2012 du 1er mai 2012 consid. 2.1).
En l'espèce, c'est à tort que le recourant prétend que les juges cantonaux n'ont pas examiné sa situation familiale; ils y ont fait référence, mais n'ont pas accordé une importance prédominante à celle-ci, ce qui ne suffit pas à en conclure à une violation du droit. La paternité du recourant et le projet de mariage qu'il invoque sont des éléments qui relèvent du bien-fondé de la décision de renvoi. Or, compte tenu des multiples condamnations pénales infligées au recourant, en particulier de la peine privative de liberté de deux ans prononcée le 23 février 2010, notamment pour infraction grave à la LStup, la décision de renvoi n'apparaît pas manifestement infondée, même si on tient compte de la naissance des deux enfants du recourant en août 2011 et de son projet de mariage (cf. <ref-ruling> consid. 4.3 et 4.4, p. 381 ss). On ne peut donc reprocher aux juges d'avoir violé l'art. 80 al. 4 LEtr ou méconnu l'art. 5 de la directive sur le renvoi, en considérant que les relations familiales du recourant n'empêchaient pas sa mise en détention administrative.
5. En dernier lieu, le recourant relève que l'autorité n'a plus entrepris de démarche en vue de l'exécution du renvoi depuis plus d'un mois. Ce faisant, il se plaint implicitement d'une violation de l'art. 76 al. 4 LEtr selon lequel les démarches nécessaires à l'exécution du renvoi ou de l'expulsion doivent être entreprises sans tarder (cf. <ref-ruling> consid. 3a p. 51; arrêt 2C_804/2008 du 5 décembre 2008 consid. 4).
Selon les faits constatés par le Tribunal cantonal, le recourant était placé en détention administrative le 7 mars 2012, l'Office fédéral des migrations s'est adressé le 12 mars 2012 à l'Ambassade du Cameroun, afin qu'elle procède à l'audition de l'intéressé. Cette audition a été fixée le 18 avril 2012. L'arrêt attaqué datant du 17 avril 2012, on ignore quelle a été son issue. Ces éléments permettent d'admettre qu'au moment où les juges cantonaux ont statué, le principe de célérité n'était manifestement pas violé.
Comme le Tribunal fédéral n'est pas un juge du fait et ne peut tenir compte de circonstances nouvelles (cf. <ref-law>), les allégations du recourant selon lesquelles aucune démarche n'a été accomplie depuis lors ne peuvent être prises en compte dans la présente procédure. En revanche, si l'inactivité des autorités alléguée par le recourant devait se poursuivre sans justification pertinente, celui-ci pourrait s'en plaindre dans le cadre d'une demande de levée de la détention formée aux conditions de l'art. 80 al. 5 LEtr.
6. Dans ces circonstances, le recours ne peut qu'être rejeté dans la mesure de sa recevabilité.
Les conclusions paraissant dès le départ vouées à l'échec, la demande d'assistance judiciaire doit être rejetée (cf. <ref-law>). Compte tenu de la situation du recourant, il ne sera toutefois pas perçu de frais (cf. <ref-law>). Aucun dépens ne sera alloué (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est rejetée.
3. Il n'est pas perçu de frais.
4. Le présent arrêt est communiqué au mandataire du recourant, au Service de la population du canton de Vaud, au Juge de paix du district de Lausanne, au Tribunal cantonal du canton de Vaud, Chambre des recours civile, et à l'Office fédéral des migrations.
Lausanne, le 19 juin 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Chatton