A.- Le 10 août 1998, l'Office fédéral des réfugiés a rejeté la seconde demande d'asile formée par X._, né en 1970, d'origine palestinienne, et sommé celui-ci de quitter la Suisse jusqu'au 30 septembre 1998 sous peine de refoulement.
Par décision du 13 février 2000, le Service cantonal valaisan de l'état civil et des étrangers (ci-après: le Service cantonal) a ordonné la mise en détention immédiate en vue du refoulement de X._ 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.
Statuant le 17 février 2000, le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a confirmé ce prononcé. Par arrêt du 28 mars 2000 (2A. 121/2000), le Tribunal fédéral a rejeté le recours formé par X._ contre ce jugement.
B.- Le 25 avril 2000, le Service cantonal a requis la prolongation, pour six mois au plus, de la détention de l'intéressé, au motif que les autorités palestiniennes et israéliennes refusaient de fournir un document de voyage.
Entendu le 10 mai 2000 par le Tribunal cantonal, X._ s'est opposé à l'admission de la requête et a conclu à sa libération immédiate. Persistant dans son refus de rentrer en Palestine, il a argué du caractère purement passif de sa résistance à l'exécution du renvoi. En outre, le Service cantonal échouait depuis au moins dix mois à obtenir un laissez-passer, que les autorités palestiniennes et israéliennes ne manifestaient nullement l'intention d'établir.
L'exécution du renvoi s'avérait dès lors impossible, de sorte qu'il devait être libéré, conformément aux art. 13c al. 5 lettre a LSEE et 5 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).
Statuant le même jour, le Tribunal cantonal a confirmé le prononcé du Service cantonal.
C.- Agissant le 8 juin 2000 par la voie du recours de droit administratif, X._ demande au Tribunal fédéral d'annuler l'arrêt rendu le 10 mai 2000 par le Tribunal cantonal et de le libérer.
Le Tribunal cantonal renonce à se déterminer. Le Service cantonal propose de rejeter le recours. X._ ne s'est pas exprimé sur cette réponse. L'Office fédéral des étrangers n'a pas déposé d'observations mais, sur invitation du Département fédéral de justice et police, l'Office fédéral des réfugiés a exposé par courrier du 21 juin 2000 les difficultés auxquelles se heurtait le renvoi des personnes d'origine palestinienne et les démarches effectuées en vue de les résoudre.

Considérant en droit :
1.- 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.
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).
Ces principes sont applicables, par analogie, lors d'un recours contre une décision de prolongation de la détention.
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, le recourant a été mis en détention en vue du refoulement au sens de l'art. 13b al. 1 lettre c LSEE, des indices concrets faisant craindre qu'il entende se soustraire à son renvoi. Statuant en dernière instance le 28 mars 2000, le Tribunal fédéral a retenu à cet égard qu'il avait été condamné le 11 novembre 1998, pour vol et dommages à la propriété, à vingt et un mois de réclusion et à huit ans d'expulsion. Après sa libération conditionnelle survenue le 10 août 1999, il ne s'était pas tenu à disposition des autorités valaisannes mais était entré dans la clandestinité.
Arrêté le 30 novembre 1999 à l'aéroport de Zurich en possession d'un faux passeport hollandais, il avait été condamné de ce chef le 3 décembre 1999 à septante-cinq jours d'emprisonnement. Enfin, il n'avait entrepris aucune démarche pour se procurer les documents d'identité ou de voyage nécessaires à l'exécution de son renvoi et avait refusé à maintes reprises de rentrer dans son pays d'origine.
Ces motifs de mise en détention subsistent. Le recourant persiste à refuser de rentrer en Palestine et de collaborer à l'obtention de ses documents de voyage, en tout cas dans la mesure où il n'a jamais écrit lui-même aux autorités palestiniennes ou israéliennes compétentes. En outre, ses fiançailles avec Y._, ressortissante suisse domiciliée à Neuchâtel, ne conduisent pas à un autre résultat.
Certes, les intéressés ont entrepris des démarches en vue de célébrer leur union, ainsi qu'en témoigne une télécopie du 17 février 2000 du Service des étrangers du canton de Neuchâtel, selon laquelle la procédure de mariage a débuté en novembre 1999, les fiancés ayant notamment déposé une "attestation de naissance" du 8 septembre 1999 établie par la Délégation Générale de Palestine à Genève. Cependant, le dossier révèle que le recourant a tenté de quitter la Suisse pour le Canada le 30 novembre 1999, de sorte que ce projet de mariage ne garantit nullement que l'intéressé soit stable et respecte les ordres des autorités suisses.
b) La détention peut ê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). Elle doit toutefois être levée 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).
aa) Selon la jurisprudence, la durée de la détention doit respecter le principe de la proportionnalité. Certes, le juge de la détention n'est pas tenu dans tous les cas de scinder la durée légale maximale en plusieurs tranches, mais il doit fixer une durée de prolongation proportionnée aux circonstances du cas concret. En ce sens, une durée de prolongation arrêtée d'emblée à six mois, qui épuise en une seule fois la durée légale maximale, doit se fonder sur des motifs particuliers. Pour déterminer cette durée, il faut notamment prendre en considération, en tenant compte du principe de la diligence (cf. art. 13b al. 3 LSEE), la complexité du cas au regard des possibilités d'exécution du renvoi et le droit du détenu à déposer, cas échéant plusieurs fois, une demande de levée de détention. Il convient ainsi d'examiner si la durée de prolongation de la détention est apte à atteindre le but fixé, soit la garantie de l'exécution du renvoi, se limite à ce qui est nécessaire à la réalisation de cet objectif et reste proportionnée en elle-même.
bb) Il ressort de l'arrêt attaqué, des écritures des parties et du dossier les éléments suivants.
Le 21 juillet 1999, le Ministère de l'Intérieur israélien a refusé de délivrer un laissez-passer à l'intéressé, au motif que celui-ci possédait un passeport ou un laissez-passer palestinien. Le 29 octobre 1999, l'Ambassade d'Israël à Berne a indiqué que ce Ministère confirmait cette réponse, qu'elle qualifiait de définitive et irrévocable. Le 14 mars 2000, l'Ambassade d'Israël a répété ne pouvoir établir de laissez-passer israélien pour l'intéressé, lequel devait utiliser son passeport ou laissez-passer palestinien. De son côté, la Délégation Générale de Palestine à Genève a déclaré le 6 mars 2000 ne pouvoir émettre de laissez-passer "dans la situation actuelle".
Par télécopie du 23 mars 2000, l'Office fédéral des réfugiés a informé le Service cantonal que les gouvernements israélien et palestinien avaient conclu une convention visant à simplifier et accélérer les retours des Palestiniens en Israël et à Gaza. Selon cet accord, les dossiers des personnes refusées devaient être transmis à la Délégation Générale de Palestine, qui les ferait suivre au Ministère de l'Intérieur israélien. Celui-ci trancherait la requête et, en cas de décision positive, inviterait l'Ambassade d'Israël à établir un laissez-passer. Cependant, la Délégation Générale de Palestine se prévalait maintenant d'un incident survenu à l'aéroport de Zurich pour refuser de transmettre les dossiers au Ministère de l'Intérieur israélien. Cette situation avait amené les autorités suisses à proposer de se passer de l'intervention des autorités palestiniennes et de déposer les dossiers auprès du Ministère de l'Intérieur israélien, directement ou par l'intermédiaire de l'Ambassade de Suisse à Tel Aviv. Toujours selon la télécopie précitée, celle-ci devait contacter les autorités israéliennes compétentes à cet effet.
cc) Force est de constater d'abord que le renvoi du recourant ne poserait pas de difficultés si celui-ci disposait d'un passeport original, et non d'une copie. Or, il est douteux que son frère ait pu égarer son passeport, ainsi que l'intéressé l'a affirmé à plusieurs reprises. Du reste, comme on l'a vu, le recourant n'a entrepris par lui-même aucune démarche en vue de se procurer un document de voyage valable.
Dans ces conditions, le retard affectant son renvoi doit, au moins dans une certaine mesure, lui être attribué.
En l'absence de passeport valable, l'obtention d'un laissez-passer est très problématique dès lors que, pour l'heure, l'octroi d'un tel document reste subordonné aux autorisations des gouvernements palestinien et israélien. Une convention a certes été conclue, mais elle n'est pas respectée par les autorités palestiniennes, qui refusent de transmettre les demandes de documents de voyage aux autorités israéliennes.
Dans ces conditions, un laissez-passer ne peut être obtenu que si les autorités palestiniennes acceptent d'exécuter la convention, ou si le Ministère de l'Intérieur israélien consent à délivrer un laissez-passer sans l'acquiescement des autorités palestiniennes, ainsi que le requièrent les autorités suisses.
Pour l'instant, on ignore le résultat des démarches accomplies par les autorités suisses, mais une issue positive n'est pas exclue dans la mesure où elles n'ont été entamées que ce printemps. L'espoir reste toutefois ténu, car seule la convention, que les autorités palestiniennes se refusent à exécuter, aurait permis de dénouer la situation bloquée au moins depuis le 21 juillet 1999. Dans ces conditions, il n'est pas possible d'admettre d'emblée que le renvoi pourra être opéré dans les six mois. Dès lors, si le renvoi n'a pu être exécuté dans un délai prolongeant la détention de trois mois, il y aura lieu de reconsidérer la situation et d'examiner si les démarches effectuées par les autorités suisses pourront aboutir avant l'échéance de la durée légale maximale de six mois. Si tel n'est pas le cas, le recourant devra alors être libéré dès le 13 août 2000.
Encore peut-on relever que, dans une télécopie adressée au Service cantonal le 15 juin 2000, soit postérieurement à l'arrêt attaqué, et dans ses observations du 21 juin 2000, l'Office fédéral des réfugiés a confirmé que la requête du recourant restait figée jusqu'à ce que la Délégation Générale de Palestine se déclare prête à la transmettre au Ministère de l'Intérieur israélien ou que les autorités suisses parviennent à un accord avec les autorités israéliennes, qui leur permettrait de déposer les dossiers au Ministère de l'Intérieur israélien, soit directement, soit par le biais de l'Ambassade de Suisse ou de l'Ambassade d'Israël.
dd) En conclusion, l'arrêt attaqué viole le principe de la proportionnalité en fixant d'emblée la durée de prolongation de la détention du recourant à six mois. Il doit donc être partiellement annulé, la détention n'étant prolongée au plus que de trois mois, à savoir jusqu'au 12 août 2000.
Encore convient-il de relever que le recourant pourra déposer une demande de levée de la détention deux mois après l'examen de la légalité de la prolongation de celle-ci (art. 13c al. 4 LSEE).
4.- Vu ce qui précède, le recours est partiellement admis.
Le recourant doit normalement supporter un émolument judiciaire réduit (art. 156 al. 1 OJ) mais, compte tenu de sa situation financière précaire, il se justifie d'y renoncer (art. 153 et 153a OJ). Il n'y a pas lieu de mettre un émolument judiciaire à charge du canton du Valais (art. 156 al. 2 OJ). Celui-ci devra en revanche verser au recourant une indemnité réduite à titre de dépens (art. 159 al. 1 OJ).

Par ces motifs,
le Tribunal fédéral :
1. Admet partiellement le recours et annule partiellement l'arrêt attaqué dans le sens où la prolongation de la détention de X._ est autorisée pour une durée de trois mois au plus, soit jusqu'au 12 août 2000.
2. Dit qu'il n'est pas perçu d'émolument judiciaire.
3. Dit que le canton du Valais versera au recourant une indemnité réduite de 800 fr. à titre de dépens.
4. Communique le présent arrêt en copie au mandataire 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 et, pour information, à l'Office fédéral des réfugiés.
_
Lausanne, le 3 juillet 2000 RED/mnv
Au nom de la IIe Cour de droit public
du TRIBUNAL FEDERAL SUISSE:
Le Président, La Greffière,