Verlängerung der Ausschaffungshaft, hat sich ergeben:
A.- Der angeblich armenische Staatsangehörige A._, geb. 7. Juni 1979, der auch unter verschie-denen anderen Namen auftritt, reiste am 9. Januar 2000 von Deutschland her, wo er bereits einen Asylantrag gestellt hatte, illegal in die Schweiz ein und ersuchte auch hier um Asyl. Am 7. Februar 2000 trat das Bundesamt für Flüchtlinge auf das Gesuch nicht ein und wies A._ mit Frist bis zum 8. Februar 2000 aus der Schweiz weg. Am 9. Februar 2000 wurde A._ den deutschen Behörden rücküberstellt.
Gleichzeitig auferlegte ihm das Bundesamt für Ausländerfragen eine Einreisesperre für zwei Jahre.
Am 2. März 2000 wurde A._ von der Kantonspolizei Zug aufgrund des Verdachts, einen Ladendiebstahl begangen zu haben, festgenommen. Er gab einen anderen Namen an und zeigte einen Ausweis, der wiederum auf einen anderen Namen lautete. Am 3. März 2000 ordnete das Kantonale Amt für Ausländerfragen des Kantons Zug die Ausschaffungshaft an, welche am 7. März 2000 vom Haftrichter am Verwaltungsgericht des Kantons Zug geprüft und bestätigt wurde.
Mit Gesuch vom 30. Mai 2000 beantragte das Kantonale Amt für Ausländerfragen, die Haft um sechs Monate zu verlängern.
Am 2. Juni 2000 verfügte der Haftrichter am Verwaltungsgericht des Kantons Zug die Haftverlängerung um sechs Monate.
B.- Mit handschriftlicher Eingabe beim Bundesgericht in russischer Sprache, welche von Amtes wegen übersetzt worden und als Verwaltungsgerichtsbeschwerde entgegenzunehmen ist, wendet sich A._ gegen die Haftverlängerung und ersucht um Freilassung.
Das Verwaltungsgericht des Kantons Zug schliesst auf Abweisung der Beschwerde. Das Kantonale Amt für Ausländerfragen beantragt Abweisung, soweit auf die Beschwerde eingetreten werden könne. Das Bundesamt für Ausländerfragen hat sich innert Frist nicht vernehmen lassen. A._ nahm die Gelegenheit nicht wahr, sich nochmals zur Sache zu äussern.

Das Bundesgericht zieht in Erwägung:
1.- Der Beschwerdeführer ersucht darum, dass das bundesgerichtliche Urteil in russischer Sprache ergehe und mit einer deutschen Übersetzung versehen werde. Gemäss Art. 37 Abs. 3 OG werden die Urteile des Bundesgerichts in einer Amtssprache, in der Regel der Sprache des angefochtenen Entscheids, verfasst. Bei der russischen Sprache handelt es sich nicht um eine schweizerische Amtssprache. Es rechtfertigt sich daher ohne weiteres, das Urteil dem angefochtenen Entscheid entsprechend in deutscher Sprache zu verfassen, zumal aus den Akten hervorgeht, dass der Beschwerdeführer auch die deutsche Sprache ein wenig versteht. Im Übrigen wird es Sache der kantonalen Behörden sein, sicherzustellen, dass das Urteil dem Beschwerdeführer verständlich gemacht wird (vgl. E. 5c).
2.- a) Gegenstand des Entscheids des Haftrichters ist einzig die Rechtmässigkeit und Angemessenheit der Haftanordnung (vgl. Art. 13c Abs. 2 ANAG). Vor dem Bundesgericht stellt sich damit lediglich die Frage der Rechtmässigkeit der Haft (vgl. Art. 104 lit. a und c OG). Namentlich ist das Bundesgericht in keiner Weise (auch nicht als Beschwerdeinstanz) zuständig, Asylbegehren zu beurteilen (vgl. insbes.
Art. 100 Abs. 1 lit. b Ziff. 2 OG) oder über Einreisesperren bzw. deren Vollzug zu befinden (vgl. Art. 100 Abs. 1 lit. b Ziff. 1 OG). Auch den Wegweisungsentscheid kann es nur dann überprüfen, wenn er - anders als hier - offensichtlich rechtswidrig ist (vgl. Art. 100 Abs. 1 lit. b Ziff. 4 OG sowie <ref-ruling> E. 2c).
Demnach ist die Verwaltungsgerichtsbeschwerde insoweit zulässig, als sie sich gegen den Entscheid über die Haftverlängerung richtet und damit die Haftfrage zum Inhalt hat. Nicht eingetreten werden kann hingegen auf die Anliegen des Beschwerdeführers im Zusammenhang mit der Einreisesperre, der Wegweisung und der Asylfrage.
b) Der Beschwerdeführer beantragt ferner, das Bundesgericht solle dafür sorgen, dass der Haftrichter, welcher das angefochtene Urteil gefällt hat, seinen Fall nicht mehr beurteile. Er macht indessen keinen Ausstandsgrund im vorliegenden Verfahren geltend. Da das Bundesgericht nur ergangene Entscheide überprüfen und nicht auf künftige Verfahren gerichtete Begehren behandeln kann, ist auch auf diesen Antrag nicht einzutreten.
3.- a) Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen, soweit die Voraussetzungen von Art. 13b ANAG erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2 S. 61; <ref-ruling> E. 3a S. 374; <ref-ruling> ff.), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist (BGE <ref-ruling> E. 3a S. 374, 377 E. 2a S. 379). Zudem muss ei-ner der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (BGE <ref-ruling> E. 3a S. 374; <ref-ruling> E. 1 S. 3). Weiter müssen die Haft verhältnismässig (<ref-ruling> E. 4 S. 383; <ref-ruling> E. 2c S. 198; vgl. auch BGE <ref-ruling> E. 3 S. 153) und die Ausschaffung rechtlich und tatsächlich möglich sein (Art. 13c Abs. 5 lit. a ANAG; vgl. <ref-ruling> E. 5 S. 384; <ref-ruling> E. 3 S. 152 ff.). Auf Seiten der Behörden ist die Papierbeschaffung mit dem nötigen Nachdruck zu verfolgen (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; <ref-ruling> ff.). Schliesslich sind die gesetzlichen Anforderungen an die Haftbedingungen zu beachten (vgl. Art. 13c Abs. 3 sowie Art. 13d ANAG; <ref-ruling>; <ref-ruling>; <ref-ruling> E. 5, 222).
Nach Art. 13b Abs. 2 ANAG darf die Haft höchstens drei Monate dauern; stehen dem Vollzug der Weg- oder Ausweisung besondere Hindernisse entgegen, so kann die Haft mit Zustimmung der kantonalen richterlichen Behörde um höchstens sechs Monate verlängert werden (Art. 13b Abs. 2 ANAG).
b) Das Amt für Ausländerfragen hat am 3. März 2000 die Ausschaffung des Beschwerdeführers nach Art. 14 ANAG verfügt und ihn damit sinngemäss auch in Anwendung von Art. 12 ANAG sofort weggewiesen. Die Ausschaffung ist zurzeit mangels Reisepapieren nicht möglich.
Beim Beschwerdeführer sind, wie der Haftrichter im angefochtenen Urteil festgestellt hat, zwei Haftgründe erfüllt. Erstens hat er trotz Einreisesperre das Gebiet der Schweiz (wieder) betreten, und er kann nicht sofort ausgeschafft werden. Der Beschwerdeführer hat gegenüber der Kantonspolizei Zug ausgesagt, die Einreisesperre sei ihm eröffnet worden, und auch in seiner Eingabe an das Bundesgericht anerkannt, er habe das Einreiseverbot für zwei Jahre verstanden; so oder so ist aber nicht wesentlich, ob er von der Einreisesperre bzw. von deren Tragweite Kenntnis hatte (vgl. <ref-ruling> E. 3a sowie AB 1997 S 1361 f. und 1998 N 536 ff.). Damit erfüllt er den Haftgrund von Art. 13b Abs. 1 lit. b in Verbindung mit Art. 13a lit. c ANAG. Zweitens belegt das bisherige Verhalten des Beschwerdeführers, dass er sich im Sinne von Art. 13b Abs. 1 lit. c ANAG (sog.
Untertauchensgefahr) nicht an behördliche Anweisungen hält, womit zu befürchten ist, er werde sich der Ausschaffung entziehen.
Dafür spricht, dass er unter mehreren Identitäten aufgetreten ist, bei der Festnahme ein falsches Ausweispapier verwendete, vor dem Haftrichter ausgesagt hat, nicht in sein angebliches Heimatland Armenien zurückkehren zu wollen, sowie dass er straffällig geworden ist (vgl. zum Haftgrund der Untertauchensgefahr BGE <ref-ruling> E. 3b/aa S. 375; <ref-ruling> E. 2a; <ref-ruling> E. 2b S. 198).
c) Die Inhaftierung als solche erscheint damit als zulässig. Dasselbe gilt grundsätzlich auch für die Verlängerung der Haft. Der Ausschaffung stehen aufgrund der mangelhaften Mitwirkung des Beschwerdeführers an der Papierbeschaffung sowie der organisatorischen Schwierigkeiten bei derselben besondere Hindernisse im Sinne von Art. 13b Abs. 2 ANAG entgegen. Bis anhin gibt es sodann keine Anhaltspunkte dafür, dass die Ausschaffung rechtlich oder tatsächlich unmöglich wäre. Weiter sind die Behörden bisher dem Beschleunigungsgebot gemäss Art. 13b Abs. 3 ANAG nachgekommen. Bereits am 6. März 2000 haben sich die kantonalen Instanzen zwecks Vollzugsunterstützung an das Bundesamt für Flüchtlinge gewandt. In der Folge haben sie das armenische Konsulat um Ausstellung eines Laissez-passer ersucht und dem Beschwerdeführer - freilich ohne Ergebnis - Gelegenheit gegeben, mehrere Telefonate zu führen, um sich ein Reisepapier zukommen zu lassen, wie er dies vorgeschlagen hatte. Am 3. Mai 2000 wurde der Beschwerdeführer erneut zwecks Papierbeschaffung befragt. Inzwischen sind Anfragen bei Interpol sowie ein (erneutes) Gesuch beim Bundesamt für Flüchtlinge um aktive Mitwirkung in Aussicht gestellt. Schliesslich ficht der Beschwerdeführer die Haftbedingungen nicht an.
d) Der Beschwerdeführer scheint noch immer der Auffassung zu sein, zu einer Freiheitsstrafe verurteilt worden zu sein. Es ist daher nochmals - wie es bereits der Haftrichter im angefochtenen Urteil getan hat - zu unterstreichen, dass es sich im vorliegenden Verfahren um fremdenpolizeiliche und damit administrative Haft zwecks Vollzugs der dem Beschwerdeführer auferlegten Wegweisung handelt. Mit der Ausschaffung wird die Haft jederzeit beendet, allenfalls auch vor Ablauf der angeordneten Haftdauer, wobei es der Beschwerdeführer in der Hand hat, durch entsprechende Mitwirkung zum baldigen Vollzug der Ausschaffung und damit zur Haftbeendigung beizutragen.
4.- a) Der Haftrichter hat die Haft im vorliegenden Fall gleich um die gesetzlich zulässige Höchstdauer von sechs Monaten verlängert. Es ist zu prüfen, ob dies mit Blick auf den Grundsatz der Verhältnismässigkeit zulässig ist.
b) Gemäss Art. 13b Abs. 2 ANAG kann die Haft um höchstens sechs Monate verlängert werden. Nach der bundesgerichtlichen Rechtsprechung bildet die Haftdauer einen Gesichtspunkt der Verhältnismässigkeit der Haft (so etwa unveröffentlichtes Urteil vom 18. April 1996 i.S. Bulic; vgl. auch Walter Kälin, Zwangsmassnahmen im Ausländerrecht: Materielles Recht, in AJP 1995 851 f.; Peter Uebersax, Menschenrechtlicher Schutz bei fremdenpolizeilicher Einsperrung, in recht 1995 54 f.). Der Haftrichter ist zwar nicht in jedem Fall verpflichtet, die zulässige Höchstdauer in mehrere Tranchen aufzuteilen. Er hat aber das Verhältnismässigkeitsprinzip zu beachten und die Dauer der Verlängerung an den Umständen des Einzelfalles zu messen. Eine Verlängerung um sechs Monate unter gleichzeitiger Ausschöpfung der gesetzlichen Höchstdauer muss sich in diesem Sinne sachlich rechtfertigen lassen. Das Bundesgericht hat eine Verlängerung um fünf Monate in einem Fall als gerade noch zulässig erachtet, in dem sich die Organisation des Wegweisungsvollzugs als besonders schwierig und die Mitwirkung des Ausländers als hartnäckig mangelhaft erwiesen (unveröffentlichtes Urteil vom 13. September 1999 i.S. Sow; vgl. auch <ref-ruling> E. 3b S. 207). Ebenfalls zu beachten sind in diesem Zusammenhang die Tragweite des Beschleunigungsgebots, die Komplexität des Falles unter Einschluss der Frage der Durchführbarkeit der Ausschaffung sowie die Möglichkeit des Inhaftierten, - allenfalls mehrmals - ein Haftentlassungsgesuch zu stellen. Es muss im Einzelfall geprüft werden, ob die verfügte Haftdauer erforderlich ist und nicht gegen das Übermassverbot, d.h. das sachgerechte und zumutbare Verhältnis von Mittel (hier: Haft) und Zweck (hier: Sicherstellung des Wegweisungsvollzugs), verstösst.
c) Im vorliegenden Fall erweist sich zwar die Organisation der Ausschaffung als schwierig und die Mitwirkung des Beschwerdeführers als ungenügend, wenn nicht sogar als bewusst auf Verzögerung ausgerichtet. Es gibt aber keinen zwingenden Anhaltspunkt dafür, dass für die Papierbeschaffung geradezu sechs Monate erforderlich wären. Sodann datiert die letzte belegte aktive Handlung der Behörden zwecks Organisation der Ausschaffung vom 3. Mai 2000, womit sie bereits im Zeitpunkt des haftrichterlichen Entscheids einen Monat zurücklag. Es handelte sich dabei um eine (wiederholte) Befragung des Beschwerdeführers zu seiner Identität und seiner Mitwirkungsbereitschaft. Weder wurden bisher hingegen Sprach- und Geographietests durchgeführt, noch wurde Interpol um Identitätsabklärung angefragt. Solche Massnahmen, wie auch ein Gesuch um intensivere Vollzugsunterstützung durch die zuständige Bundesbehörde, sind freilich neuerdings in Aussicht gestellt. Unter diesen Umständen erscheint es als angebracht, dass innert vernünftiger Frist eine erneute haftrichterliche Kontrolle stattfindet, wobei unter anderem zu prüfen sein wird, ob die Behörden weiterhin - insbesondere im Hinblick auf die in Aussicht gestellten zusätzlichen Bemühungen, soweit sich diese tatsächlich als sinnvoll und erfolgversprechend erweisen - das Beschleunigungsgebot einhalten.
Unerlässlich ist auch eine erneute Prüfung der Frage innert angemessener Frist, ob die Ausschaffung weiterhin überhaupt möglich erscheint. Eine solche Kontrolle ist im vorliegenden Fall bei einer Haftverlängerung von sechs Monaten nicht gewährleistet. Wohl hat der Beschwerdeführer die Möglichkeit, ein Haftentlassungsgesuch gemäss Art. 13c Abs. 4 ANAG zu stellen. Das ersetzt aber die zwingende haftrichterliche Überprüfung von Amtes wegen nicht. Zudem dürften dem rechtsunkundigen Beschwerdeführer nicht alle einschlägigen Zusammenhänge, etwa bei der Haftvoraussetzung der rechtlichen und tatsächlichen Durchführbarkeit der Ausschaffung, bekannt und geläufig sein.
Hinzu kommt, dass der Beschwerdeführer im vorliegenden Verfahren nicht durch einen Anwalt vertreten ist, was auch schon vor dem Haftrichter zutraf. Grundsätzlich besteht bei der Haftverlängerung ein Anspruch auf Beigabe eines unentgeltlichen Rechtsvertreters, wenn auch nicht von Amtes wegen (unveröffentlichtes Urteil vom 6. Mai 1997 i.S. El Hady), so doch auf Gesuch hin (BGE <ref-ruling>). Der Beschwerdeführer hat keinen entsprechenden Antrag gestellt, sodass ihm kein Rechtsbeistand beigegeben werden musste. Dass der Beschwerdeführer aber nicht anwaltlich vertreten war und ist, rechtfertigt angesichts der recht komplexen Ausgangslage - weniger im Hinblick auf den Haftgrund als im Hinblick auf die Durchführbarkeit der Ausschaffung - eine erneute haftrichterliche Kontrolle innert nicht allzu langer Frist umso mehr.
Es erweist sich damit als nicht erforderlich und als Verstoss gegen das Übermassverbot, die Ausschaffungshaft des Beschwerdeführers unmittelbar um die Höchstdauer von sechs Monaten zu verlängern.
d) Angesichts der Umstände des vorliegenden Falles rechtfertigt sich demgegenüber eine Haftverlängerung um drei Monate. Damit ist gewährleistet, dass innert sachgerechter Frist eine erneute richterliche Überprüfung der Haft stattfindet, sollte der Beschwerdeführer bis dahin nicht ausgeschafft werden können und sollte das Kantonale Amt für Ausländerfragen ihn dannzumal weiterhin in Haft behalten wollen.
Es ist zu unterstreichen, dass nach Ablauf dieser drei Monate eine erneute Haftverlängerung durchaus in Betracht fällt, sofern die entsprechenden Voraussetzungen weiterhin erfüllt sein sollten. Darüber wird gegebenenfalls wiederum auf Antrag des Kantonalen Amts für Ausländerfragen hin der Haftrichter zu entscheiden haben.
e) Abschliessend ist festzuhalten, dass die Möglichkeit des Beschwerdeführers, gemäss Ziff. 2 des Dispositivs des angefochtenen Entscheids bzw. gemäss Art. 13c Abs. 4 ANAG im gegebenen Zeitpunkt ein Haftentlassungsge-such zu stellen, vom vorliegenden Urteil nicht berührt wird.
5.- a) Demnach ist die Verwaltungsgerichtsbeschwerde in dem Sinne teilweise gutzuheissen, dass die Ausschaffungshaft lediglich um drei Monate, d.h. - bei einer Laufzeit von sechs Monaten ab erster Inhaftierung am 3. März 2000 - bis zum 2. September 2000, verlängert wird. Im Übrigen muss die Verwaltungsgerichtsbeschwerde abgewiesen werden, soweit darauf eingetreten werden kann.
b) Mit Blick auf die finanziellen Verhältnisse des Beschwerdeführers rechtfertigt es sich auch insoweit, als er unterliegt (vgl. Art. 156 Abs. 1 und 3 OG), von der Erhebung einer Gerichtsgebühr abzusehen (Art. 153a Abs. 1 OG). Der Kanton Zug hat ohnehin keine Kosten zu tragen (Art. 156 Abs. 2 OG).
c) Das Kantonale Amt für Ausländerfragen wird ersucht, sicherzustellen, dass das vorliegende Urteil dem Beschwerdeführer korrekt eröffnet und verständlich gemacht wird.

Demnach erkennt das Bundesgericht:
1.- a) Die Verwaltungsgerichtsbeschwerde wird teilweise gutgeheissen und das Urteil des Haftrichters am Verwaltungsgericht des Kantons Zug vom 2. Juni 2000 in dem Sinne abgeändert, dass die Ausschaffungshaft des Beschwerdeführers lediglich bis zum 2. September 2000 verlängert wird.
b) Im Übrigen wird die Verwaltungsgerichtsbeschwerde abgewiesen, soweit darauf einzutreten ist.
2.- Es werden keine Kosten erhoben.
3.- Dieses Urteil wird dem Beschwerdeführer, dem Kantonalen Amt für Ausländerfragen (KAFA) des Kantons Zug und dem Verwaltungsgericht des Kantons Zug, Haftrichter, sowie dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 21. Juni 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident: Der Gerichtsschreiber: