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.