Faits:
A. Ressortissant du Sénégal né en 1987, X._ a déposé une demande d'asile en Suisse qui a fait l'objet d'une décision de non-entrée en matière rendue par l'Office fédéral des migrations le 11 avril 2012. Cette décision ordonnait le renvoi de X._ en Italie, où l'affaire devait être traitée sur le fond. Elle prévoyait également que le requérant devait quitter la Suisse au plus tard le jour suivant l'échéance du délai de recours, faute de quoi il s'exposait à des moyens de contrainte.
Il ressort du dossier que cette décision a été notifiée à X._ le 23 avril 2012.
B. Le même jour, soit 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._ immédiatement en détention administrative, pour trois mois au plus.
Le 26 avril 2012, l'intéressé a été entendu par le Juge unique de la Cour de droit public du Tribunal cantonal valaisan (ci-après: le Juge unique). Il a répété qu'il acceptait de retourner en Italie prétendant également ignorer que sa demande d'asile ne serait vraisemblablement pas admise. A la suite de cette audition, le Juge unique a, par arrêt du 26 avril 2012, 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 auprès du Tribunal fédéral, dans lequel il conteste sa mise en détention, indiquant qu'il ne comprend pas sur quels motifs elle se fonde. Il déclare également vouloir se plier à l'injonction de quitter la Suisse pour se rendre en Italie dès sa libération.
Le Service cantonal a transmis son dossier, sans observations. Le Tribunal cantonal et l'Office fédéral des migrations ont renoncé à se déterminer.

Considérant en droit:
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 2D_66/2011 du 13 décembre 2011 consid. 1; 2C_935/2011 du 7 décembre 2011 consid. 1.1), peu importe que le recourant n'ait pas expressément mentionné cette voie de droit dans son écriture (cf. <ref-ruling> consid. 1.2 p. 302 s.; arrêt 2C_349/2011 du 23 novembre 2011 consid. 1.2, non publié in <ref-ruling>).
Interjeté en temps utile (cf. art. 100 al. 1 LTF), par le détenu qui a qualité pour agir (cf. art. 89 al. 1 LTF), le présent recours est en principe recevable, dès lors que, même si la formulation est sommaire, le recourant conteste de manière suffisamment claire l'existence de motifs justifiant sa détention (cf. art. 42 al. 2 LTF). Il convient donc d'entrer en matière.
2. Pour confirmer la mise en détention administrative du recourant portant sur une durée de trois mois, l'arrêt attaqué s'est fondé sur l'art. 76 al. 1 let. b ch. 3 et 4 LEtr. A l'appui de cette décision, le Juge unique souligne que l'intéressé est entré illégalement en Suisse pour y demander un asile qu'il savait ne pouvoir espérer, son assertion du contraire étant jugée peu crédible. L'on ne peut ainsi pronostiquer que, s'il était libéré, le recourant se plierait à l'exécution de son renvoi et ne passerait pas dans la clandestinité.
Il convient de s'interroger sur le bien-fondé de ces motifs, le recourant contestant, pour sa part, avoir adopté un comportement justifiant sa mise en détention administrative.
3. 3.1 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 (ANDREAS AUER/GIORGIO MALINVERNI/MICHEL HOTTELIER, Droit constitutionnel suisse, vol. II 2e éd., Berne 2006, p. 161 N 348). 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 (cf. THOMAS HUGI YAR, Zwangsmassmahmen im Ausländerrecht, in: Ausländerrecht, Bâle 2009, p. 424 s. N 10.7).
3.2 L'art. 76 al. 1 let. b ch. 3 et 4 LEtr retenu dans l'arrêt attaqué prévoit que, 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êt 2C_963/2010 du 11 janvier 2011 consid. 2.1) ou à se rendre dans le pays compétent pour se prononcer sur sa demande d'asile en vertu des accords de Dublin (cf. arrêt 2C_952/2011 du 19 décembre 2011 consid. 3.3). 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êt 2C_675/2011 du 20 septembre 2011 consid. 2.1).
3.3 En l'espèce, l'arrêt attaqué ne contient aucun élément tangible permettant d'en inférer que le recourant serait sur le point de partir dans la clandestinité et/ou n'entendrait pas se plier à l'injonction qui lui est faite de se rendre en Italie. Le Juge unique retient seulement que le recourant était entré illégalement en Suisse et que son assertion, selon laquelle il ignorait qu'il ne pourrait obtenir l'asile en Suisse, était peu crédible. On voit mal comment on peut en déduire des indices concrets que le recourant tente de se soustraire à l'exécution de son renvoi et parte dans la clandestinité. Il n'a pas été constaté que le recourant ait donné une fausse identité; celui-ci a par ailleurs toujours déclaré qu'il acceptait de retourner en Italie, ce qu'il a encore confirmé au Juge unique lors de son audition. On peut ajouter que le dossier ne contient aucun élément concret propre à justifier une détention en application des art. 76 al. 1 let. b ch. 3 ou 4 LEtr et que les autorités n'ont pas présenté d'observations qui mettraient en évidence de tels éléments.
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. En particulier, on ne voit pas que le recourant remplisse un des cas de figure énumérés à l'art. 75 LEtr auxquels l'art. 76 al. 1 let. b ch. 1 LEtr renvoie. En outre, la décision de non-entrée en matière des autorités en matière d'asile datée du 11 avril 2012 est fondée sur l'art. 34 al. 2 let. d LAsi, de sorte qu'elle n'est pas visée par l'art. 76 al. 1 let. b ch. 2 LEtr et aucun indice ne laisserait supposer que le renvoi serait imminent, ce qui exclut les motifs prévus aux ch. 5 et 6 de l'art. 76 al. 1 let. b LEtr.
3.4 Il en découle qu'aucun des motifs justifiant la mise en détention administrative en vue du renvoi énumérés à l'art. 76 al. 1 let. b LEtr n'est réalisé dans le cas d'espèce. Partant, la mise en détention du recourant est illicite et celui-ci doit être libéré immédiatement.
4. 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). Il ne sera pas alloué de dépens, le recourant n'ayant pas fait appel à un représentant (cf. art. 68 al. 1 LTF).

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. Le recourant est immédiatement libéré.
3. Il n'est pas perçu de frais ni alloué de dépens.
4. Le présent arrêt est communiqué au recourant, au Service de la population et des migrations du canton du Valais, au Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais et à l'Office fédéral des migrations.
Lausanne, le 22 mai 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Chatton