Faits : A. Ressortissant ghanéen né en 1994, X._ a déposé une demande d'asile, laquelle s'est soldée par un refus d'entrée en matière, entré en force en mars 2013 (cf. arrêt 2C_593/2013 du 27 juin 2013). Le 4 mai 2015, il a été condamné par le Tribunal du IIème arrondissement pour les districts d'Herens et de Conthey (Valais) pour infraction grave à la loi fédérale du 3 octobre 1951 sur les stupéfiants et les substances psychotropes (LStup; RS 812.121) à une peine privative de liberté de 36 mois, sous déduction de la détention avant jugement déjà effectuée. B. Par décision du 13 mai 2016, après le prononcé de la libération conditionnelle de l'intéressé avec effet au 14 mai 2016, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a placé celui-ci en détention administrative pour une durée de trois mois au plus en vue de son renvoi au Ghana. Entendu le 17 mai 2016 devant le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Juge unique), X._ a déclaré qu'il ne parlerait pas tant qu'il n'avait pas d'avocat et qu'il s'opposait à son renvoi. Par arrêt du 17 mai 2016, le Juge unique a approuvé la mise en détention de l'intéressé. C. Par courrier reçu le 25 mai 2016, X._ forme un recours au Tribunal fédéral contre l'arrêt du 17 mai 2016. Il conclut, en substance, à l'annulation de l'arrêt attaqué et à ce que sa libération soit ordonnée. Le Tribunal cantonal a renoncé à se déterminer. Le Secrétariat d'Etat aux migrations (SEM) a formulé des observations et s'est rallié, pour le surplus, à l'arrêt attaqué.