A.- X._, ressortissant d'Albanie né en 1972, a été interpellé à Brig le 21 mars 2000.
Le 23 mars 2000, le Service cantonal valaisan de l'état civil et des étrangers (ci-après: le Service cantonal) a ordonné le refoulement immédiat à la frontière de X._ au motif qu'il était entré en Suisse sans visa et y avait séjourné illégalement.
Par décision du même jour, le Service cantonal a ensuite ordonné la mise en détention immédiate en vue du refoulement de X._ pour trois mois au plus, en vertu de l'art. 13b al. 1 lettre c de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 142. 20), des indices faisant craindre qu'il entende se soustraire au renvoi. En effet, démuni de moyens d'existence personnels et réguliers, l'intéressé était entré en Suisse sans papiers d'identité ni visa. Il avait en outre pénétré par effraction dans une cabane de montagne, où il avait volé des vêtements et des chaussures.
Ce prononcé a été confirmé le lendemain par le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) au motif que les circonstances de l'arrivée de l'intéressé en Suisse dénotaient une habitude de la clandestinité qui suffisait à remplir les réquisits de l'art. 13b al. 1 lettre c LSEE.
B.- Par lettre datée du 20 avril 2000, X._ a requis la levée de sa détention.
Entendu le 28 avril 2000 par le Tribunal cantonal, l'intéressé a maintenu sa requête.
C.- Par arrêt du 28 avril 2000, le Tribunal cantonal a refusé de libérer X._, considérant que la situation ne s'était pas sensiblement modifiée depuis la mise en détention.
En outre, les autorités albanaises traitaient les demandes de laissez-passer avec plus de célérité quand l'identité des intéressés était certaine.
D.- Agissant lui-même par lettre non datée, parvenue au Tribunal fédéral le 4 mai 2000 et rédigée en albanais, X._ conclut en substance à l'annulation de l'arrêt du Tribunal cantonal du 28 avril 2000 et à sa libération immédiate.
Le Tribunal cantonal renonce à se déterminer. Le Service cantonal propose le rejet du recours. L'Office fédéral des étrangers n'a pas déposé d'observations. De son côté, l'intéressé ne s'est pas exprimé sur la réponse des autorités cantonales.

Considérant en droit :
1.- a) Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2a p. 16, 253 consid. 1a p. 254).
Selon l'art. 108 al. 2 OJ, le recours de droit administratif doit contenir les conclusions, motifs et moyens de preuve. La motivation doit être topique, à savoir se rapporter au litige en question (<ref-ruling> ss). Lorsqu'il s'agit d'un recours formé sans l'aide d'un professionnel contre l'approbation d'une mise en détention, le Tribunal fédéral ne pose pas d'exigences élevées de motivation (cf.
<ref-ruling> consid. 3b p. 277). Il suffit que l'on puisse déduire de l'acte de recours, comme en l'espèce, que l'intéressé s'oppose à sa détention.
Par ailleurs, s'il est vrai que le présent recours est rédigé en albanais, en violation de l'art. 30 al. 1 OJ, il a été traduit par les soins du Tribunal fédéral, de sorte qu'il est recevable de ce point de vue.
Dans ces conditions, respectant les autres conditions des art. 97 ss OJ, le recours est recevable.
b) Conformément à l'art. 104 lettre a OJ, le recours de droit administratif peut être formé pour violation du droit fédéral, y compris l'excès et l'abus du pouvoir d'appréciation.
Le Tribunal fédéral revoit d'office l'application du droit fédéral qui englobe notamment les droits constitutionnels du citoyen (<ref-ruling> consid. 2 p. 211; <ref-ruling> consid. 1b p. 11). Comme il n'est pas lié par les motifs que les parties invoquent, il peut admettre le recours pour d'autres raisons que celles avancées par le recourant ou, au contraire, confirmer l'arrêt attaqué pour d'autres motifs que ceux retenus par l'autorité intimée (art. 114 al. 1 in fine OJ; <ref-ruling> consid. 1b p. 477 et les arrêts cités, voir aussi <ref-ruling> consid. 2b p. 109).
En revanche, lorsque le recours est dirigé, comme en l'occurrence, contre la décision d'une autorité judiciaire, le Tribunal fédéral est lié par les faits constatés dans la décision, sauf s'ils sont manifestement inexacts ou incomplets ou s'ils ont été établis au mépris de règles essentielles de procédure (art. 104 lettre b et 105 al. 2 OJ; <ref-ruling> consid. 1c p. 635). Aussi la possibilité d'alléguer des faits nouveaux ou de faire valoir de nouveaux moyens de preuve est-elle très restreinte (<ref-ruling> consid. 3a p. 221; <ref-ruling> consid. 3a p. 420; <ref-ruling> consid. 1c p. 99; <ref-ruling> consid. 8b p. 33; Fritz Gygi, Bundesverwaltungsrechtspflege, 2e éd., Berne 1983, p. 286/287).
Ainsi, en principe, saisi d'un recours contre une décision de détention en vue du refoulement, le Tribunal fédéral se fonde uniquement sur l'état de fait tel qu'il se présentait devant le juge de la détention. Il ne saurait tenir compte des faits que le recourant n'a pas expressément allégués devant cette autorité ou qui ne ressortaient pas manifestement des pièces alors déposées. Les faits nouveaux doivent être pris en considération par le juge cantonal de la détention (pour autant que les conditions d'une révision ne soient pas remplies) lors de l'examen d'une demande de levée de détention ou, une fois écoulés les trois mois de détention, dans le cadre d'une procédure de prolongation de celle-ci (<ref-ruling> consid. 3a p. 221).
2.- Selon l'art. 13b al. 1 LSEE, lorsqu'une décision de renvoi ou d'expulsion de première instance a été notifiée à un étranger, l'autorité cantonale compétente peut, aux fins d'en assurer l'exécution, mettre cette personne en détention, en particulier lorsque "des indices concrets font craindre qu'elle entend se soustraire au refoulement, notamment si son comportement jusqu'alors mène à conclure qu'elle se refuse à obtempérer aux instructions des autorités" (lettre c; sur les indices de danger de fuite, voir notamment <ref-ruling> consid. 2a p. 50/51 et Alain Wurzburger, La jurisprudence récente du Tribunal fédéral en matière de police des étrangers, in: RDAF 53/1997 I, p. 267 ss, spéc.
p. 332/333). La légalité et l'adéquation de la détention doivent être examinées dans les nonante-six heures au plus tard par une autorité judiciaire au terme d'une procédure orale (art. 13c al. 2 LSEE). Une demande de levée de détention peut être déposée un mois plus tard (art. 13c al. 4 LSEE). A cet égard, le juge de la détention doit examiner si les motifs de détention subsistent, même lorsque l'étranger n'a pas recouru contre la décision initiale de mise en détention (art. 13c al. 5 lettre a LSEE); il peut toutefois se référer à la motivation de ce prononcé (cf. <ref-ruling> consid. 3b p. 277). La détention doit être levée lorsque les autorités n'ont pas entrepris avec la diligence requise les démarches nécessaires à l'exécution du renvoi ou de l'expulsion (art. 13b al. 3 LSEE), ou lorsque l'exécution du renvoi ou de l'expulsion s'avère impossible pour des raisons juridiques ou matérielles (art. 13c al. 5 lettre a LSEE). Enfin, selon l'art. 13c al. 3 LSEE, le juge de la détention tient compte de la situation familiale de la personne détenue et des conditions d'exécution de la détention (voir, sur l'ensemble de ces points, les arrêts cités in <ref-ruling> consid. 3a p. 374).
3.- Le recourant demande à être libéré afin de "chercher un travail, pour assurer sa propre subsistance ou rentrer en Albanie".
a) Le recourant a été mis en détention administrative le 23 mars 2000 afin d'éviter qu'il se soustraie à son refoulement (art. 13b al. 1 lettre c LSEE).
aa) Des indices suffisants permettent de conclure à un danger de fuite.
En premier lieu, le recourant a adopté un comportement pénalement répréhensible car, accompagné d'un compatriote, il est entré par effraction dans une cabane de montagne et y a dérobé des vêtements et des chaussures. Du reste, par ordonnance pénale du 22 mars 2000 entrée en force et figurant au dossier, le recourant a été condamné pour vol (et entrée illégale en Suisse) à un mois d'emprisonnement avec sursis.
Or, selon la jurisprudence, un étranger condamné pénalement est en principe plus susceptible qu'une personne sans antécédents judiciaires de se soustraire à l'avenir aux injonctions de l'autorité (<ref-ruling> consid. 2b p. 198). Certes, le recourant explique avoir été poussé par la fatigue et le froid, mais cet élément ne saurait être pris en considération par le Tribunal fédéral, car le juge pénal en a déjà tenu compte.
Puis, si le recourant affirme avoir dû se résigner à jeter son passeport - ce document ayant été soi-disant trempé pendant la traversée de l'Adriatique au point d'être illisible -, ses déclarations à cet égard sont contradictoires, partant, peu crédibles. En effet, selon le dossier, le recourant a affirmé le 21 mars 2000 s'en être débarrassé à son arrivée à Bari, alors qu'il allègue maintenant avoir agi de la sorte à la frontière italo-suisse.
De plus, le recourant ne s'est pas contenté de refuser de coopérer à l'obtention de documents de voyage, mais a tenté de faire obstruction à l'action des autorités en s'engageant à effectuer des démarches qu'il n'a finalement pas accomplies. Ainsi, d'après le dossier, il a déclaré le 21 mars 2000 à la police cantonale pouvoir demander à son père résidant en Albanie de lui procurer une attestation d'identité.
En revanche, il a affirmé le 24 mars 2000 au Tribunal cantonal qu'il refusait de s'adresser à sa famille à ce propos, sous prétexte que celle-ci lui créerait des ennuis en apprenant sa mise en détention. Par ailleurs, il paraît douteux qu'un cousin séjournant en Italie consente à se déplacer à cet effet en Albanie, comme le recourant l'a prétendu le même jour.
Enfin, le recourant est démuni de tout moyen d'existence en Suisse.
bb) D'un autre côté, le recourant ne s'oppose pas, apparemment, à son rapatriement en Albanie. Selon le dossier, il a affirmé le 24 mars 2000 au Tribunal cantonal qu'il souhaitait "rentrer au plus vite en Albanie". Cette volonté a été confirmée le 20 avril 2000 dans sa requête de levée de détention, puis le 28 avril 2000 devant le Tribunal cantonal.
Enfin, il demande maintenant à ce qu'un délai de vingt-quatre heures lui soit accordé afin de quérir lui-même un laissez-passer auprès de la représentation albanaise en Suisse.
Toutefois, d'après le dossier, il a déclaré le 21 mars 2000 à la police cantonale qu'il entendait travailler en Europe; ce but apparaissant difficile à réaliser, il préférait rentrer en Albanie plutôt que d'être incarcéré. Dans ces circonstances, sa volonté affirmée de rapatriement est sujette à caution, dès lors qu'elle semble ne se manifester que par opposition à une détention. Le recourant paraît surtout intéressé à travailler, sinon en Suisse, du moins en Europe, ce qui n'est pas contredit par son écriture de recours.
Du reste, son peu d'empressement à obtenir un laissez-passer tend à conforter cette présomption.
cc) Dans ces conditions, il est douteux qu'une fois libéré, le recourant reste à disposition des autorités en vue de son renvoi, de sorte que le risque de fuite au sens de l'art. 13b al. 1 lettre c LSEE subsiste.
b) Par ailleurs, il ressort du dossier que les autorités ont mené avec la diligence voulue les démarches en vue d'obtenir un laissez-passer, dès lors que, le 28 mars 2000, la police cantonale a demandé à la représentation albanaise en Suisse de délivrer un tel document.
Au demeurant, selon ses observations, le Service cantonal a encore requis le 11 mai 2000 - postérieurement à l'arrêt attaqué - la nouvelle Division chargée des rapatriements de l'Office fédéral des réfugiés (cf. ordonnance du 11 août 1999 sur l'exécution du renvoi et de l'expulsion d'étrangers [OERE; RS 142. 281], entrée en vigueur le 1er octobre 1999), de solliciter la représentation suisse en Albanie d'examiner l'identité de l'intéressé.
De plus, rien ne laisse supposer que ces démarches ne pourraient aboutir avant l'échéance des trois mois de détention, d'autant que, pour l'instant, l'identité du recourant est présumée correcte.
Enfin, le recourant ne s'étant pas plaint des conditions de sa détention, il n'y a pas lieu de traiter ce point.
c) En conséquence, il sied de confirmer le maintien en détention du recourant.
4.- Vu ce qui précède, le recours est mal fondé et doit être rejeté. Succombant, le recourant devrait en principe supporter les frais judiciaires (art. 156 al. 1 OJ). Compte tenu de sa situation financière précaire, il se justifie cependant de statuer sans frais (art. 153 et 153a OJ).

Par ces motifs,
le Tribunal fédéral :
1. Rejette le recours.
2. Dit qu'il n'est pas perçu d'émolument judiciaire.
3. Communique le présent arrêt en copie au recourant, au Service de l'état civil et des étrangers et au Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'au Département fédéral de justice et police.
_
Lausanne, le 23 mai 2000 RED/mnv
Au nom de la IIe Cour de droit public
du TRIBUNAL FEDERAL SUISSE:
Le Président,
La Greffière,