A.- Par décision du 1er octobre 1996, l'Office fédéral des réfugiés a rejeté la demande d'asile formée par Z._, soi-disant ressortissant angolais né en 1963.
Statuant sur recours le 12 décembre 1999, la Commission suisse de recours en matière d'asile a confirmé ce refus et a imparti à l'intéressé un délai de départ au 6 avril 2000.
Le canton du Valais, auquel Z._ avait été affecté, a annoncé le 7 mars 2000 à l'Office fédéral des réfugiés que l'intéressé avait disparu depuis la veille.
Répondant à une requête de la fiancée de l'intéressé, B._, ressortissante canadienne, l'Office fédéral des réfugiés a indiqué le 30 mars 2000 que Z._ était toujours considéré comme disparu et devait se présenter à bref délai aux autorités valaisannes.
Le 31 mars 2000, les fiancés ont informé le Service cantonal valaisan de l'état civil et des étrangers (ci-après:
le Service cantonal) qu'ils vivaient ensemble à La Chaux-de-Fonds.
Par prononcé du 10 avril 2000, l'Office fédéral des réfugiés a rejeté la requête de Z._ visant à prolonger le délai de départ en vue de se marier. En effet, seule une décision positive de l'office de l'état civil au terme de la procédure préparatoire aurait pu justifier un tel report.
L'intéressé restait néanmoins en droit de demander ultérieurement, auprès d'une représentation suisse à l'étranger, une autorisation d'entrée à des fins de mariage.
B.- Le 2 mai 2000, Z._ a été conduit à Sion.
Entendu par la police cantonale valaisanne, il a contesté avoir disparu dans la clandestinité, dès lors qu'il avait communiqué sa nouvelle adresse au Service cantonal. Il admettait toutefois ne pas avoir obtempéré à une convocation l'invitant à se présenter aux autorités valaisannes, expliquant cette omission par la peur et le souci d'assister sa fiancée, qui relevait alors d'une opération. Sa carte d'identité avait été déposée auprès des autorités d'asile, mais les autorités angolaises, se fondant sur une copie, l'avait tenue pour fausse. Il ne disposait ainsi d'aucun document d'identité ou de voyage et n'avait du reste accompli aucune démarche en vue d'en obtenir. Enfin, il refusait de rentrer en Angola, alléguant que sa vie y était en danger.
Par décision du même jour, le Service cantonal a ordonné la mise en détention immédiate en vue du refoulement de Z._ pour une durée de 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 que l'intéressé entende se soustraire à son renvoi.
Entendu le 5 mai 2000 par le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal), Z._ a persisté dans son refus de rentrer en Angola, ou dans un autre pays d'Afrique, ajoutant s'être volontairement abstenu de retirer à la poste les plis recommandés qu'il présumait concerner l'issue de ses procédures d'asile ou l'organisation de son départ. Il admettait en outre que ses assertions sur la composition de sa famille restée en Angola ne correspondaient pas entièrement à celles données aux autorités d'asile en 1996.
Statuant le même jour, le Tribunal cantonal a confirmé le prononcé du Service cantonal. Il relevait en bref l'obstination de l'intéressé à demeurer en Suisse malgré les décisions des autorités d'asile, ses déclarations contradictoires sur sa famille, son essai de différer son renvoi en s'abstenant de retirer des lettres pouvant s'y rapporter et l'opinion concordante sur sa carte d'identité des autorités angolaises et de l'Office fédéral des réfugiés, celui-ci ayant déclaré le 10 décembre 1999 ne pas en garantir l'authenticité.
C.- Agissant le 26 mai 2000 par la voie du recours de droit administratif, Z._, représenté par sa fiancée, demande en substance au Tribunal fédéral d'annuler l'arrêt rendu le 5 mai 2000 par le Tribunal cantonal, de lever sa détention, au moins à titre conditionnel, et d'annuler la décision de renvoi. Il requiert en outre l'audition de témoins, dont celle de sa fiancée.
Le Service cantonal et le Tribunal cantonal concluent au rejet du recours. L'Office fédéral des étrangers n'a pas déposé d'observations. Z._ s'est exprimé sur la réponse du Service cantonal et a maintenu ses conclusions.

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).
La décision attaquée a été prise par une autorité judiciaire statuant en dernière instance cantonale au sens de l'art. 98 lettre g OJ, elle échappe aux exceptions prévues aux art. 98 à 102 OJ - en particulier à l'art. 100 al. 1 lettre b OJ - et elle est fondée sur le droit public fédéral.
Déposé en temps utile et dans les formes prescrites, le présent recours est donc en principe recevable en vertu des art. 97 ss OJ.
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). En particulier, les modifications ultérieures de l'état de fait ne peuvent normalement pas être prises en considération, car on ne saurait reprocher à une autorité d'avoir mal constaté les faits, au sens de l'art. 105 al. 2 OJ, lorsque ceux-ci ont changé après sa décision (<ref-ruling> consid. 3a p. 221).
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).
c) Le recourant requiert, à titre de moyens de preuves, l'audition de sa fiancée et celle d'autres témoins qu'il ne désigne pas. Cette requête doit toutefois être rejetée, car le dossier est suffisamment instruit sur tous les éléments déterminants pour que le Tribunal fédéral puisse vérifier la bonne application du droit fédéral. Il n'y a donc pas lieu d'ordonner une procédure probatoire (art. 95 OJ applicable en vertu de l'art. 113 OJ).
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). En principe, la durée de la détention ne peut excéder trois mois; toutefois, elle peut, avec l'accord de l'autorité judiciaire cantonale, être prolongée de six mois au maximum, si des obstacles particuliers s'opposent à l'exécution du renvoi ou de l'expulsion (art. 13b al. 2 LSEE). La détention est subordonnée à la condition que les autorités entreprennent sans tarder les démarches nécessaires à l'exécution du renvoi ou de l'expulsion (art. 13b al. 3 LSEE). Enfin, selon l'art. 13c al. 5 lettre a LSEE, elle doit être levée lorsque son motif n'existe plus ou que l'exécution du renvoi ou de l'expulsion s'avère impossible pour des raisons juridiques ou matérielles (voir, sur l'ensemble de ces points, les arrêts cités in <ref-ruling> consid. 3a p. 374).
3.- a) En l'espèce, l'autorité intimée a retenu à juste titre que le comportement du recourant faisait craindre qu'il se soustraie à son refoulement.
aa) Le recourant refuse de rentrer dans son pays et n'a pas respecté le délai de départ fixé au 6 avril 2000.
Certes, il n'a pas disparu dans la clandestinité dès lors qu'il a finalement informé le 31 mars 2000 les autorités cantonales qu'il résidait à La Chaux-de-Fonds chez sa fiancée.
Il n'en demeure pas moins qu'il a quitté le territoire valaisan sans autorisation et qu'il a attendu trois semaines avant de révéler sa nouvelle adresse aux autorités cantonales. De plus, il n'a pas obtempéré, sans justification valable, à une convocation du Service cantonal. Surtout, il a tenté d'éluder et de retarder son renvoi en refusant de retirer les courriers qui lui étaient adressés à cet effet.
bb) En outre, sa nationalité et son identité sont incertaines.
Comme l'a retenu l'autorité intimée, l'Office fédéral des réfugiés a informé l'office de l'état civil de La Chaux-de-Fonds, par courrier du 10 décembre 1999, qu'il ne garantissait pas l'authenticité de la carte d'identité dont il lui remettait copie pour la procédure de mariage. Les autorités angolaises n'ont pas davantage reconnu la validité de ce document. De même, dans une lettre adressée le 28 mars 2000 à la représentation suisse en Angola, versée au dossier, le Service de surveillance de l'état civil du canton de Neuchâtel a relevé que les deux extraits de naissance en sa possession ne se référaient pas au même registre des naissances.
Enfin, le recourant ne conteste pas s'être contredit quant à la composition de sa famille.
Certes, le recourant a exposé le 5 mai 2000 à l'autorité intimée, selon le procès-verbal figurant au dossier, que le refus des autorités angolaises de reconnaître sa carte d'identité était compréhensible, car seule une copie du recto de ce document leur avait été envoyée, de sorte que son lieu d'émission n'y figurait pas. Ces cartes avaient de plus changé dans l'intervalle. S'agissant des divergences entre les extraits de naissance, le recourant les attribue dans ses observations à la négligence des employés angolais. Ces arguments ne suffisent toutefois pas à convaincre de la véracité de son identité.
cc) Les intentions de mariage du recourant ne conduisent pas à un autre résultat.
Il est vrai que les intéressés ont entrepris des démarches en vue de célébrer leur union, ainsi qu'en témoigne une attestation du 28 mars 2000, déposée au dossier, du Service de surveillance de l'état civil du canton de Neuchâtel, selon lequel les pièces versées à cette fin par les fiancés sont en cours de vérification auprès de la représentation suisse en Angola. De même, la fiancée du recourant le représente dans la procédure ici en cause et a requis, ainsi que sa famille, l'autorisation de lui rendre visite en détention, ce qui tend à établir l'intensité de ses sentiments. Toutefois, selon le courrier du 31 mars 2000 figurant au dossier, les fiancés ne se sont rencontrés que le 29 août 1999, soit il y a moins de dix mois. De plus, aucun d'eux n'a la nationalité suisse et, même s'ils souhaitent vivre leur union en Suisse, cela ne garantit pas suffisamment que le recourant soit stable et respecte les ordres des autorités suisses.
b) Les autorités cantonales ont satisfait à leur obligation de diligence imposée par l'art. 13b al. 3 LSEE, consistant à effectuer rapidement les démarches propres à déterminer l'identité et à obtenir les papiers nécessaires au renvoi de l'intéressé, avec ou sans sa collaboration (Andreas Zünd, Die Rechtsprechung des Bundesgerichts zu den Zwangsmassnahmen im Ausländerrecht, in: ZBJV 132/1996 p. 89).
Par télécopie du 15 février 2000, figurant au dossier, la police cantonale a requis la Division rapatriements de l'Office fédéral des réfugiés de présenter l'intéressé aux autorités angolaises le 6 ou 7 mars 2000. Cette audition n'a toutefois pas pu avoir lieu, l'intéressé ayant disparu.
En outre, par télécopie du 24 mai 2000 postérieure à l'arrêt attaqué, versée au dossier, la police cantonale a sollicité la Division rapatriements précitée d'inscrire l'intéressé sur la liste des cas prioritaires. Dans ses observations du 8 juin 2000, le Service cantonal a déclaré que le recourant devait être présenté aux autorités angolaises le 15 juin 2000 à Berne.
Enfin, le Service cantonal s'est régulièrement enquis des progrès des démarches effectuées par les autorités neuchâteloises de l'état civil.
c) Il reste à examiner si, conformément à l'art. 13c al. 5 lettre a LSEE, l'exécution du renvoi ne s'avère pas impossible pour des raisons juridiques ou matérielles.
Constituent des motifs juridiques s'opposant au renvoi le principe de non-refoulement ou le fait que l'exécution du renvoi ne peut être raisonnablement exigée (art. 14a al. 3 et 4 LSEE). Le pouvoir d'examen du juge de la détention est toutefois restreint à cet égard: seules font l'objet de la procédure ouverte devant lui la légalité et l'adéquation de la mise en détention elle-même (cf. art. 13c al. 2 LSEE), à l'exclusion des questions relevant de l'asile ou du renvoi, sur lesquelles les autorités compétentes de police des étrangers statuent de manière définitive (art. 100 al. 1 lettre b ch. 4 et 5 OJ et art. 105 de la loi fédérale du 5 octobre 1979 sur l'asile [LAsi; RS 142. 31]). Dans ces conditions, le juge ne doit refuser d'approuver l'ordre de détention que lorsque la décision de renvoi apparaît manifestement inadmissible (cf. <ref-ruling> consid. 2c p. 62; voir aussi <ref-ruling> consid. 2 p. 220).
Le recourant conteste la décision de renvoi en invoquant ses projets de mariage.
Ceux-ci ne lui permettent toutefois pas d'obtenir une autorisation de séjour. En effet, l'art. 8 de la Convention européenne de sauvegarde des droits de l'homme et des libertés fondamentales du 4 novembre 1950 (CEDH; RS 0.101), qui seul peut s'appliquer à cet égard aux fiancés, à l'exclusion des art. 7 et 17 LSEE, suppose que le fiancé résidant en Suisse y bénéficie d'un droit de présence (cf. <ref-ruling> consid. 1e p. 5, 289 consid. 1c p. 292), que les intéressés entretiennent depuis longtemps des relations étroites et effectivement vécues et qu'il existe des indices concrets d'un mariage sérieusement voulu et imminent (cf. Luzius Wildhaber, Internationaler Kommentar zur Europäischen Menschenrechtskonvention, n. 350 ad art. 8; Mark E. Villiger, Handbuch der Europäischen Menschenrechtskonvention, Zurich 1999, n. 559, p. 328).
En l'occurrence, la fiancée ne bénéficie que d'une autorisation de séjour annuelle, ainsi qu'en atteste la copie de celle-ci figurant au dossier. De plus, le recourant ne démontre pas l'imminence de la célébration. Les difficultés auxquelles se heurtent son identification laissent plutôt présager le contraire. Du reste, dans ses déterminations du 8 juin 2000, le Service cantonal relève que le Service de surveillance de l'état civil du canton de Neuchâtel vient de lui confirmer que les certificats de naissance et la carte d'identité n'ont pas encore été authentifiés par la représentation suisse en Angola. Certes, dans ses observations du 12 juin 2000, le recourant affirme qu'un employé de celle-ci l'a informé la veille que la vérification était achevée et n'attendait plus que la signature de la personne compétente, alors en vacances. Toutefois, en l'absence de tout document écrit, ce seul allégué n'établit pas à satisfaction de droit l'imminence du mariage.
Encore peut-on relever que, par prononcé du 10 avril 2000, l'Office fédéral des réfugiés a refusé de prolonger le délai de départ du recourant en vue de son mariage.
Enfin, vu les efforts coordonnés des autorités valaisannes, neuchâteloises et fédérales afin d'identifier l'intéressé, on ne saurait affirmer que le laissez-passer nécessaire ne pourra être obtenu en temps utile.
d) En conclusion, le Tribunal cantonal était fondé à placer le recourant en détention en vertu de l'art. 13b al. 1 lettre c LSEE. 4.- Vu ce qui précède, le recours est mal fondé et doit être rejeté. Succombant, le recourant doit supporter les frais judiciaires (art. 156 al. 1 OJ).

Par ces motifs,
le Tribunal fédéral :
1. Rejette le recours.
2. Met à la charge du recourant un émolument judiciaire de 1'000 fr.
3. Communique le présent arrêt en copie à la représentante du 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'à l'Office fédéral des étrangers.
_
Lausanne, le 22 juin 2000 RED/elo
Au nom de la IIe Cour de droit public
du TRIBUNAL FEDERAL SUISSE:
Le Président,
La Greffière,