Faits:
A. Né en 1991, X._ prétend être un ressortissant soudanais.
Par décision du 9 juin 2010 entrée en force, l'Office fédéral des migrations (ci-après: l'Office fédéral) n'est pas entré en matière sur la demande d'asile déposée par X._, prononçant le renvoi du requérant de Suisse d'ici au 9 juillet 2010. Il a été précisé que le canton du Valais devait procéder à l'exécution.
Le 1er septembre 2010, X._ a été condamné par le Tribunal de Sion à vingt mois de peine privative de liberté et à une amende de 200 fr., sous déduction de la détention préventive pour violation grave de la législation fédérale sur les stupéfiants et défaut d'avis en cas de trouvaille.
Le 27 janvier 2011, l'Office fédéral a rejeté la demande de reconsidération déposée par l'intéressé à l'encontre de la décision du 9 juin 2010, en soulignant que ses assertions sur son origine n'étaient pas crédibles.
Par décision transmise à X._ le 9 mai 2011, 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 une durée de trois mois au plus, après avoir entendu l'intéressé, qui avait déclaré ne pas vouloir regagner le Soudan, n'être en possession d'aucun document prouvant son identité et vouloir se rendre en Italie.
Par arrêt du 11 mai 2011 rendu par le Juge unique, le Tribunal cantonal valaisan (ci-après: le Tribunal cantonal) a approuvé la décision du Service cantonal du 9 mai 2011.
B. A l'encontre de l'arrêt du 11 mai 2011, X._ déclare former un recours auprès du Tribunal fédéral, au terme duquel il demande un suivi médical, la révocation de la détention administrative et sa remise en liberté immédiate, avant d'en savoir plus sur ses origines.
Le Tribunal cantonal a renoncé à se déterminer. Le Service cantonal a transmis son dossier sans observation. L'Office fédéral ne s'est pas prononcé et X._ n'a pas fourni d'observations complémentaires.

Considérant en droit:
1. 1.1 Le recourant n'a pas précisé par quelle voie de droit il s'adresse au Tribunal fédéral. Ceci ne saurait toutefois lui nuire, si son écriture remplit les conditions de recevabilité de la voie de droit normalement ouverte (cf. <ref-ruling> consid. 1.2 p. 302 s.), soit en l'occurrence, s'agissant d'une mesure de contrainte, du recours en matière de droit public (<ref-law>; arrêt 2C_10/2009 du 5 février 2009 consid. 2, non publié aux <ref-ruling>).
1.2 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 par le recourant qui, placé en détention, a indéniablement qualité pour agir (<ref-law>). Il est donc en principe recevable (<ref-law>).
2. La détention du recourant a été ordonnée le 9 mai 2011 par le Service cantonal. Elle a été confirmée par le Tribunal cantonal le 11 mai suivant, après audition de l'intéressé. Le délai impératif de 96 heures prévu à l'art. 80 al. 2 LEtr a donc été respecté.
3. 3.1 La mise en détention du recourant se fonde sur l'art. 76 al. 1 let. b ch. 3 et 4 LEtr. Cette disposition prévoit entre autres 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 que celle-ci entende se soustraire au renvoi, en particulier parce qu'elle ne se soumet pas à son obligation de collaborer, ou si son comportement permet de conclure qu'elle se refuse à obtempérer aux instructions des autorités. D'après la jurisprudence, un risque de fuite existe notamment 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_956/2010 du 11 janvier 2011 consid. 2.2). Comme cela ressort de 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_131/2011 du 25 février 2011 consid. 3.2.1; 2C_945/2010 du 5 janvier 2011 consid. 2.1).
3.2 Pour justifier la détention, l'arrêt attaqué retient entre autres éléments que le recourant a fait des déclarations sur ses frères et soeurs qui ne correspondaient pas à celles ressortant du dossier de la procédure d'asile.
Comme la Cour de céans a déjà eu l'occasion de le rappeler au Juge unique valaisan dans plusieurs affaires (cf. arrêts 2C_963/2010 du 11 janvier 2011 consid. 2.2; 2C_945/2010 du 5 janvier 2011 consid. 2.2), les indications erronées d'un étranger sur sa fratrie sont impropres à fonder une mise en détention en vertu de l'art 76 al. 1 let. b ch. 3 et 4 LEtr. En effet, sans autre explication figurant dans l'arrêt attaqué, l'on ne voit pas que de fausses informations relatives aux frères et soeurs soient de nature à rendre l'exécution du renvoi plus difficile, voire à l'empêcher. Un tel motif pour justifier une détention administrative est donc contraire au droit fédéral.
3.3 Il ressort toutefois de l'arrêt attaqué que d'autres motifs ont été pris en compte. Ainsi, il a été retenu que le recourant n'a fourni aucun document d'identité et a donné des indications sur son origine qui n'étaient pas crédibles. En outre, bien que sommé de quitter la Suisse à la suite du refus d'entrer en matière sur sa demande d'asile du 9 juin 2010, il n'a pas obtempéré. Lors de son audition devant le Juge unique, il a expressément confirmé qu'il refusait de rentrer dans son pays. Enfin, il a fait l'objet d'une condamnation pénale pour infraction grave à la loi fédérale sur les stupéfiants. Sur la base de ces éléments, il existe un risque manifeste que le recourant parte dans la clandestinité et se soustraie à son obligation de quitter la Suisse, ce qui permet de justifier la détention en application de l'art. 76 al. 1 let. b ch. 3 et 4 LEtr.
4. Se prévalant de la jurisprudence du Tribunal fédéral et de l'art. 5 par. 1 let. f CEDH, le recourant soutient qu'il doit être libéré, dès lors que l'exécution de son renvoi au Soudan est impossible, puisque l'autorité ne dispose d'aucun élément pour prouver sa véritable identité et qu'il n'y a pas d'accord permettant le renvoi avec cet Etat.
4.1 S'il s'avère que l'exécution du renvoi ou de l'expulsion est impossible pour des raisons juridiques ou matérielles, la détention doit être levée (cf. art. 80 al. 6 let. a LEtr). La jurisprudence a récemment rappelé que ces raisons doivent être importantes ("triftige Gründe") et qu'il ne suffit pas que l'exécution du renvoi soit momentanément impossible (par exemple faute de papiers d'identité), tout en restant envisageable dans un délai prévisible. L'exécution du renvoi doit être qualifiée d'impossible lorsque le rapatriement est pratiquement exclu, même si l'identité et la nationalité de l'étranger sont connues et que les papiers requis peuvent être obtenus (arrêts 2C_974/2010 du 11 janvier 2011 consid. 3.1; 2C_538/2010 du 19 juillet 2010 consid. 3.1). Tel est par exemple le cas si le déplacement de la personne concernée n'est pas concevable pour des raisons de santé ou qu'un Etat refuse de façon univoque de reprendre certains de ses ressortissants (<ref-ruling> consid. 2 p. 220; arrêt 2C_473/2010 du 25 juin 2010 consid. 4.1).
Dans tous les cas, la durée de la détention, envisagée dans son ensemble, doit apparaître proportionnée (<ref-ruling> consid. 2.2 p. 100; <ref-ruling> consid. 1 p. 58). Il convient en particulier de vérifier, en fonction des circonstances concrètes, si la détention en vue d'assurer l'exécution d'un renvoi au sens de l'art. 5 par. 1 let. f CEDH est (encore) adaptée et nécessaire (<ref-ruling> consid. 2.3.1 p. 96 s.; arrêt 2C_974/2010 du 11 janvier 2011 consid. 3.1 in fine).
4.2 En l'occurrence, il est vrai que le renvoi du recourant paraît momentanément ne pas pouvoir être exécuté, dès lors que celui-ci n'a jamais produit de documents d'identité et que sa nationalité n'est pas établie, lui-même ayant formulé des assertions non crédibles sur son origine soudanaise. Il ne s'agit toutefois pas de raisons qui, en l'état de la procédure, sont suffisamment importantes pour considérer que le renvoi est impossible dans un délai prévisible. En effet, il n'est pas exclu que les autorités parviennent rapidement à déterminer l'origine du recourant, avec l'aide d'un spécialiste de provenance, et puissent organiser le retour dans son pays.
Au surplus, l'argumentation du recourant qui, pour démontrer l'impossibilité de son renvoi, soutient que les autorités ne disposent d'aucun élément permettant de prouver sa véritable identité, qu'aucun accord n'existe entre la Suisse et le Soudan permettant son renvoi et qu'au surplus, les autorités suisses ne savent pas d'où il vient, confine à la témérité. En effet, ces obstacles proviennent précisément du refus de l'intéressé de fournir des indications exactes et de collaborer avec les autorités, en violation de l'art. 90 LEtr. C'est du reste notamment en raison de ce manque de collaboration que le recourant a été placé en détention (cf. art. 76 al. 1 let. b ch. 3 LEtr).
Quoi qu'il en soit, aucun élément ne permet de considérer que les autorités ne vont pas être prochainement en mesure de déterminer l'origine exacte du recourant. L'on ne peut ainsi affirmer, en l'état de la procédure, que le renvoi serait impossible au sens de l'art. 80 al. 6 LEtr.
4.3 En outre, le recourant a été placé en détention en vue de son renvoi le 9 mai 2011 et, comme l'a retenu le Juge cantonal, rien ne laisse à penser pour l'instant que les efforts des autorités ne continueront pas avec la diligence voulue (cf. art. 76 al. 4 LEtr). La décision attaquée, qui prévoit une détention de trois mois, apparaît donc nécessaire pour assurer l'exécution du renvoi, est conforme au principe de la proportionnalité et ne viole pas l'art. 5 par. 1 let. f CEDH.
5. Le recourant soutient qu'il n'a rien mangé depuis sa mise en détention et demande un suivi médical. Il convient de le rendre attentif au fait qu'en vertu de l'art. 25 de la loi cantonale valaisanne d'application du 15 novembre 1996 de la loi fédérale sur les mesures de contrainte en matière de droit des étrangers (LALMC/VS; RS/VS 142.4), celui-ci peut demander à être examiné par un médecin (cf. arrêt 2C_956/2010 du 11 janvier 2011 consid. 3.2). Dès lors qu'il ne soutient pas avoir formulé une telle requête qui lui aurait été arbitrairement refusée, il n'appartient pas à la Cour de céans d'entrer plus avant sur ce point. Au demeurant, le Tribunal fédéral n'examine les conditions de la détention que dans la mesure où les griefs y relatifs ont été soulevés devant le Juge cantonal (<ref-ruling> consid. 3a p. 221; arrêt 2C_128/2009 du 30 mars 2009 consid. 3.2). Or, l'arrêt attaqué ne contient rien à ce sujet et le recourant ne prétend nullement qu'il se serait plaint auprès du Juge cantonal de ne pas avoir été examiné par un médecin.
6. Dans ces circonstances, le recours doit être rejeté. Succombant, le recourant devrait en principe supporter les frais judiciaires (art. 66 al. 1, 1ère phrase, LTF). Compte tenu de sa situation, il se justifie cependant de statuer sans frais (cf. art. 66 al. 1, 2e phrase, LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Il n'est pas perçu de frais judiciaires.
3. Le présent arrêt est communiqué au recourant, 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 9 juin 2011
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Chatton