Faits:
A. Ressortissante camerounaise née en 1981, X._ a vu sa demande de prolongation de permis de séjour définitivement refusée par le Tribunal cantonal valaisan le 18 mai 2011. Le délai initial de départ qui lui avait été fixé pour quitter la Suisse a été prolongé au 1er janvier 2012.
B. Le 23 avril 2012, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a placé X._ en détention pour trois mois au plus.
Le 26 avril 2012, l'intéressée a été entendue par le Juge unique de la Cour de droit public du Tribunal cantonal valaisan (ci-après: le Juge unique). Celle-ci a contesté la légalité de sa détention et a affirmé vouloir attendre en Suisse la fin de la procédure de divorce, alléguant des éléments démontrant son intégration dans le pays. Elle a aussi fait état de démarches auprès de l'ambassade camerounaise en vue de remplacer son passeport égaré et avoir demandé au Service cantonal l'autorisation de poursuivre son séjour en Suisse.
A la suite de l'audition du 26 avril 2012, le Juge unique a, par arrêt rendu le même jour, approuvé la décision de mise en détention prononcée par le Service cantonal le 23 avril précédent.
C. Contre l'arrêt du 26 avril 2012, X._ dépose un recours en matière de droit public auprès du Tribunal fédéral, en concluant à l'admission du recours et à sa libération immédiate.
Par ordonnance présidentielle du 21 mai 2012, le Tribunal fédéral a rejeté la requête de mesures provisionnelles formée par la recourante tendant à sa libération immédiate.
Le Service cantonal a transmis son dossier, sans observations. Le Juge unique a présenté des déterminations. L'Office fédéral des migrations a renoncé à se déterminer. Les observations finales de X._ sont parvenues au Tribunal fédéral passé le délai qui lui avait été imparti à cet effet (cf. ch. 3 du dispositif de l'ordonnance présidentielle du 21 mai 2012).

Considérant en droit:
1. 1.1 En matière de mesures de contrainte, la décision rendue en dernière instance cantonale par le Juge unique valaisan peut faire l'objet d'un recours en matière de droit public au Tribunal fédéral (cf. notamment arrêts 2C_413/2012 du 22 mai 2012 consid. 1; 2D_66/2011 du 13 décembre 2011 consid. 1). Le présent recours ayant été interjeté en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par la recourante qui, placée en détention administrative, remplit à l'évidence les conditions de l'<ref-law>, il convient donc d'entrer en matière.
1.2 L'examen du Tribunal fédéral se fonde 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 (cf. <ref-ruling> consid. 4.2 p. 560; <ref-ruling> consid. 4.3 p. 62) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Aucun fait nouveau ni preuve nouvelle ne peut en principe être présenté devant le Tribunal de céans (<ref-law>).
2. La recourante invoque en premier lieu une violation de l'art. 76 LEtr, reprochant au Juge unique d'avoir confirmé sa mise en détention, sans avoir examiné s'il existait des éléments concrets faisant craindre qu'elle se soustraie à son renvoi, ce que par ailleurs elle contestait.
2.1 Comme le Tribunal fédéral l'a récemment rappelé, la détention administrative porte une atteinte grave à la liberté personnelle et ne peut être ordonnée que dans le respect de l'art. 5 CEDH (cf. <ref-ruling> consid. 2.2.1 p. 107) et de l'art. 31 Cst., ce qui suppose en premier lieu qu'elle repose sur une base légale. Le respect de la légalité implique ainsi que la mise en détention administrative ne soit prononcée que si les motifs prévus dans la loi sont concrètement réalisés (arrêt 2C_413/2012 du 22 mai 2012 consid. 3.1).
2.2 La décision entreprise se fonde sur l'art. 76 al. 1 let. b ch. 3 et 4 LEtr, selon lequel lorsqu'une décision de renvoi a été notifiée, l'autorité compétente peut, afin d'en assurer l'exécution, mettre en détention la personne concernée si des éléments concrets font craindre qu'elle entende se soustraire au renvoi ou à l'expulsion, en particulier parce qu'elle ne se soumet pas à son obligation de collaborer (cf. ch. 3) ou si son comportement permet de conclure qu'elle se refuse à obtempérer aux instructions des autorités (cf. ch. 4).
Selon la jurisprudence, ces motifs 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_413/2012 du 22 mai 2012 consid. 3.2 in fine; 2C_675/2011 du 20 septembre 2011 consid. 2.1).
Ne constituent pas des éléments suffisants le seul fait que l'étranger est entré en Suisse de façon illégale ou le fait qu'il soit démuni de papiers d'identité (cf. <ref-ruling> consid. 4.2.1 p. 146 s.). De même, le fait de ne pas quitter le pays dans le délai imparti à cet effet n'est pas à lui seul suffisant pour admettre un motif de détention au sens de l'art. 76 al. 1 ch. 3 ou 4 LEtr, mais peut tout au plus constituer un indice parmi d'autres en vue d'établir un risque de fuite (cf. arrêts 2A.208/1998 du 29 avril 1998 consid. 3; 2A.514/1997 du 9 décembre 1997 consid. 1b; ALAIN WURZBURGER, La jurisprudence récente du Tribunal fédéral en matière de police des étrangers, in: RDAF 1997 I 267 ss, p. 332 s.; THOMAS HUGI YAR, Zwangsmassnahmen im Ausländerrecht, in: Ausländerrecht [Peter Uebersax et al. (éd.)], 2e éd., Bâle 2009, p. 417 ss, 463 N 10.84). En effet, si tel était le cas, il aurait appartenu au législateur d'indiquer expressément à l'art. 76 al. 1 LEtr que le non-respect du délai de départ constitue à lui seul un motif justifiant la mise en détention de l'étranger.
A l'inverse, la circonstance que la personne concernée s'est tenue, assez longtemps et de manière ininterrompue, en un endroit stable à la disposition des autorités plaide en défaveur du risque de fuite (cf. arrêt 2A.514/1997 du 9 décembre 1997 consid. 1b, cité par: ANDREAS ZÜND, ad art. 76 LEtr, in: Migrationsrecht [Marc Spescha et al. (éd.)], 3e éd., Zurich 2012, p. 215 N 6).
2.3 En l'espèce, les faits retenus dans la décision entreprise ne permettent pas de saisir quels sont les indices concrets qui démontreraient que la recourante entend se soustraire à son renvoi ou qu'elle se refuse à obtempérer aux injonctions des autorités.
En effet, le Juge unique a commencé par examiner les objections formulées par la recourante à sa mise en détention: il a relevé que les critiques revenant à contester la légalité de son renvoi n'avaient plus à être examinées, pas plus que celles relatives à une future interdiction d'entrée. Puis, il a indiqué : "qu'il est constant que, depuis l'entrée en force de l'arrêt du 7 octobre 2011, la détenue ne s'est guère préoccupée de préparer son départ, tout en affirmant ne pas s'y opposer, et qu'elle est restée dans le pays, nonobstant son obligation de le quitter". Il en a déduit que cette attitude ne laissait guère présager que la recourante persisterait à demeurer à disposition des autorités qui ont désormais cessé de se montrer patientes à son égard, ni qu'elle ne cherchera pas à se cacher pour se soustraire à l'exécution de son renvoi. Dans ses déterminations, il a souligné que ce comportement suffisait à en inférer, selon l'expérience et le bon sens, une volonté arrêtée de demeurer dans le pays et constituait un élément concret au sens de l'art. 76 al. 1 let. b ch. 3 LEtr.
Une telle position ne peut être suivie. En l'absence de tout élément tangible sous réserve du maintien de la recourante en Suisse, de telles suppositions ne sauraient constituer des "indices concrets" propres à justifier une détention administrative en application de l'art. 76 al. 1 ch. 3 et 4 LEtr.
En outre, rien dans le dossier ne permet à la Cour de céans, en application de l'<ref-law>, d'en tirer l'existence d'éléments tangibles qui permettent d'admettre un risque que la recourante parte dans la clandestinité ou qu'elle se refuse à obtempérer aux injonctions des autorités. Il ressort au contraire des déclarations de la recourante lors de son audition auprès du Juge unique que celle-ci a toujours décliné son identité, qu'elle a noué des liens en Valais et qu'elle y a exercé une activité professionnelle d'aide-soignante. En outre, la recourante a dit accepter de rentrer dans son pays d'origine, son avocat ayant par ailleurs souligné qu'un ami de la recourante, dont il a cité le nom, était prêt à régler le prix du billet d'avion voire à se porter caution. La recourante a aussi allégué s'être rendue auprès de l'Ambassade du Cameroun pour y accomplir les démarches en vue d'obtenir le remplacement de son passeport égaré et a affirmé avoir envoyé des affaires en Afrique deux semaines auparavant. Face à de telles déclarations et en l'absence de toute injonction ou délai fixé à la recourante par les autorités pour qu'elle se conforme à son obligation de quitter la Suisse, force est d'admettre que la détention ne remplit pas les conditions de l'art. 76 al. 1 let. b ch. 3 et 4 LEtr. En outre, les faits constatés ne permettent pas de retenir l'existence d'un autre motif de mise en détention en vue du renvoi parmi la liste énumérée à l'art. 76 al. 1 let. b LEtr.
Par conséquent, la mise en détention de la recourante est illicite et celle-ci doit être libérée immédiatement.
3. Compte tenu de l'issue du litige, il n'y a pas lieu de percevoir de frais judiciaires (cf. art. 66 al. 1 et 4 LTF). Le canton du Valais sera condamné à verser à la recourante, représentée par un avocat, une indemnité à titre de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'arrêt du 26 avril 2012 est annulé.
2. La recourante est immédiatement libérée.
3. Le canton du Valais versera à la recourante une indemnité de 2'000 fr. à titre de dépens.
4. Le présent arrêt est communiqué au mandataire de la recourante, au Service de la population et des migrations et au Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 14 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