Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. X._, geb. 1980, Staatsangehöriger von Moldawien, reiste am 2. Dezember 2003 zusammen mit drei Landsmännern in Chiasso illegal in die Schweiz ein. Die vier Männer entwendeten einen Personenwagen und wurden in Y._ von der Polizei verhaftet. Mit Verfügung vom 3. Dezember 2003 wurde X._ aus der Schweiz weggewiesen, und das Kantonale Amt für Ausländerfragen Zug ordnete gegen ihn die Ausschaffungshaft an, die vom Haftrichter des Verwaltungsgerichts des Kantons Zug mit Verfügung vom 5. Dezember 2003 für die Dauer von drei Monaten bis zum 1. März 2004 bestätigt wurde.
Am 26. Februar 2004 ersuchte das Kantonale Amt für Ausländerfragen den Haftrichter des Verwaltungsgerichts des Kantons Zug um Zustimmung zu einer Verlängerung der Ausschaffungshaft um drei Monate. Mit Verfügung vom 1. März 2004 stimmte die Haftrichterin der Verlängerung der Ausschaffungshaft bis zum 1. Juni 2004 zu.
Mit am 12. März 2004 zur Post gegebenem Schreiben in moldawischer Sprache (Eingang beim Bundesgericht 15. März 2004), welches von Amtes wegen übersetzt wurde (Eingang der Übersetzung beim Bundesgericht am 19. März 2004), äussert sich X._ im Wesentlichen zu seiner Einreise in die Schweiz und zur Situation in seinem Heimatland, wobei er zumindest sinngemäss Beendigung der Haft beantragt. Die Eingabe ist als Verwaltungsgerichtsbeschwerde entgegenzunehmen.
Es ist weder ein Schriftenwechsel noch sind weitere Instruktionsmassnahmen (wie Einholen der kantonalen Akten) angeordnet worden. Über die Beschwerde wird im vereinfachten Verfahren (Art. 36a OG) befunden.
Es ist weder ein Schriftenwechsel noch sind weitere Instruktionsmassnahmen (wie Einholen der kantonalen Akten) angeordnet worden. Über die Beschwerde wird im vereinfachten Verfahren (Art. 36a OG) befunden.
2. 2.1 Wurde ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger und (z.B. wegen fehlender Reisepapiere) nicht sofort durchführbarer Weg- oder Ausweisungsentscheid eröffnet, so kann die zuständige kantonale Behörde (Art. 13c Abs. 1 ANAG) einen Ausländer mit Zustimmung der zuständigen kantonalen richterlichen Behörde (Art. 13c Abs. 2 ANAG) zur Sicherstellung von dessen Vollzug in Ausschaffungshaft nehmen, wenn die Voraussetzungen von Art. 13b ANAG (s. auch Art. 13c Abs. 3 und Abs. 5 ANAG) erfüllt sind, insbesondere wenn ein gesetzlicher Haftgrund gemäss Art. 13b Abs. 1 ANAG vorliegt. Die Haft darf vorerst für höchstens drei Monate angeordnet werden; 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). Dabei muss die Aufrechterhaltung bzw. Verlängerung der Haft weiterhin verhältnismässig sein (vgl. <ref-ruling>; <ref-ruling> E. 4 S. 383), und der Vollzug der Wegweisung darf nicht aus rechtlichen oder tatsächlichen Gründen inzwischen als undurchführbar gelten (vgl. Art. 13c Abs. 5 lit. a ANAG; <ref-ruling> E. 1 S. 219 mit Hinweisen). Dazu ist unerlässlich, dass die für den Vollzug der Weg- oder Ausweisung notwendigen Vorkehrungen umgehend getroffen werden (Art. 13b Abs. 3 ANAG, Beschleunigungsgebot; vgl. <ref-ruling>).
2.2 Der Beschwerdeführer ist aus der Schweiz weggewiesen worden. Wohl gibt er zu verstehen, dass er in der Schweiz ein Asylgesuch stellen will. Selbst die Ausführungen, die er heute, mehrere Monate nach seiner Anhaltung, hierzu macht, weisen darauf hin, dass es ihm weniger um Schutz vor behördlicher Verfolgung in seiner Heimat, sondern vielmehr darum geht, den (insbesondere in wirtschaftlicher und offenbar auch in familiärer Hinsicht) schwierigen Verhältnissen in seiner Heimat zu entgehen. Dafür, dass er bereits bei seiner Festnahme und damit vor Erlass der Wegweisungsverfügung mit genügender Klarheit zu erkennen gegeben hätte, dass er aus asylrechtlichen Gründen in die Schweiz gekommen war, gibt es unter diesen Umständen keine Anzeichen. Jedenfalls ist von einer gültigen, der Überprüfung durch das Bundesgericht entzogenen Wegweisungsverfügung (zum Verhältnis fremdenpolizeirechtliche Wegweisung/Asylgesuch vgl. <ref-ruling> E. 2c S. 61 f. und E. 3 S. 63 ff.) auszugehen, zur Sicherstellung von deren Vollzug Ausschaffungshaft angeordnet werden kann, wenn die übrigen Voraussetzungen erfüllt sind.
2.2 Der Beschwerdeführer ist aus der Schweiz weggewiesen worden. Wohl gibt er zu verstehen, dass er in der Schweiz ein Asylgesuch stellen will. Selbst die Ausführungen, die er heute, mehrere Monate nach seiner Anhaltung, hierzu macht, weisen darauf hin, dass es ihm weniger um Schutz vor behördlicher Verfolgung in seiner Heimat, sondern vielmehr darum geht, den (insbesondere in wirtschaftlicher und offenbar auch in familiärer Hinsicht) schwierigen Verhältnissen in seiner Heimat zu entgehen. Dafür, dass er bereits bei seiner Festnahme und damit vor Erlass der Wegweisungsverfügung mit genügender Klarheit zu erkennen gegeben hätte, dass er aus asylrechtlichen Gründen in die Schweiz gekommen war, gibt es unter diesen Umständen keine Anzeichen. Jedenfalls ist von einer gültigen, der Überprüfung durch das Bundesgericht entzogenen Wegweisungsverfügung (zum Verhältnis fremdenpolizeirechtliche Wegweisung/Asylgesuch vgl. <ref-ruling> E. 2c S. 61 f. und E. 3 S. 63 ff.) auszugehen, zur Sicherstellung von deren Vollzug Ausschaffungshaft angeordnet werden kann, wenn die übrigen Voraussetzungen erfüllt sind.
2.3 2.3.1 Die kantonalen Behörden stützen die Haft auf den Haftgrund von Art. 13b Abs. 1 lit. c ANAG. Danach kann der Ausländer in Ausschaffungshaft genommen werden, wenn konkrete Anzeichen befürchten lassen, dass er sich der Ausschaffung entziehen will, insbesondere weil sein bisheriges Verhalten darauf schliessen lässt, dass er sich behördlichen Anordnungen widersetzt (Haftgrund der "Untertauchensgefahr", Kriterien zusammengefasst in <ref-ruling> E. 2a S. 50 f.; s. auch <ref-ruling> E. 4.2 S. 146 ff.; <ref-ruling> E. 3b/aa S. 375).
Der Beschwerdeführer ist illegal in die Schweiz eingereist. Er und seine Begleiter haben sofort nach der Einreise einen Personenwagen entwendet, was zeigt, dass ihnen jedes Mittel recht ist, um sich ihr Fortkommen in der Schweiz zu erleichtern. Im Übrigen hat der Beschwerdeführer unmissverständlich seinen Willen zum Ausdruck gebracht, in der Schweiz oder sonst wo in Westeuropa zu Geld zu kommen. Seine bisherigen Äusserungen den Behörden gegenüber sowie die Ausführungen in der Beschwerdeschrift lassen klar erkennen, dass er eine Rückkehr in sein Heimatland in jedem Fall ausschliesst, unabhängig vom Bestehen allfälliger Asylgründe (s. vorstehend E. 2.2). Unter diesen Umständen ist seine Weigerung, in sein Heimatland zurückzukehren, nicht asylrechtlich begründet, und sie muss als Anzeichen dafür gewertet werden, dass er sich den Behörden für die Organisation und den Vollzug der Wegweisung nach einem für ihn negativen Abschluss des Asylverfahrens nicht zur Verfügung halten würde. Der Haftgrund von Art. 13b Abs. 1 lit. c ANAG ist erfüllt.
2.3.2 Die Behörden haben sich bisher kontinuierlich bemüht, die für den Wegweisungsvollzug erforderlichen Abklärungen zu treffen (s. Sachverhaltsteil der angefochtenen Verfügung lit. B). Demgegenüber lässt der Beschwerdeführer jede Bereitschaft vermissen, an der Vorbereitung der Rückreise mitzuwirken. Obwohl mithin dem Beschleunigungsgebot nachgelebt wurde, konnte die Ausschaffung noch nicht organisiert werden. Damit stehen dem Wegweisungsvollzug besondere Hindernisse entgegen, weshalb eine Haftverlängerung zulässig ist, sofern die Ausschaffung nicht als undurchführbar gelten muss, wovon vorliegend nicht auszugehen ist:
Die Haft ist gestützt auf Art. 13c Abs. 5 lit. a ANAG nur dann zu beenden, wenn für die Undurchführbarkeit des Vollzugs der Wegweisung triftige Gründe sprechen oder praktisch feststeht, dass sich die Ausschaffung innert der gesetzlichen Höchstdauer der Haft kaum wird realisieren lassen (<ref-ruling> E. 2c S. 172; <ref-ruling> E. 2 S. 220). Die Vorgehensweise der Schweizer Behörden sowie die Reaktion der moldawischen Botschaft lassen erkennen, dass die Identitätsabklärungen auf gutem Weg sind, und es ist nicht ersichtlich, warum die notwendigen Reisepapiere innert absehbarer Frist nicht sollten erhältlich gemacht werden können. Wohl wird durch das nunmehr eingeleitete Asylverfahren eine gewisse Verzögerung eintreten. Abgesehen davon, dass das nachträgliche Asylgesuch die zuvor ausgesprochene Wegweisung und damit die Möglichkeit der Ausschaffungshaft nicht dahinfallen lässt (<ref-ruling> E. 2b S. 380 mit Hinweis), darf unter den vorliegenden Umständen (s. vorstehend E. 2.2) davon ausgegangen werden, dass über das prioritär an die Hand zu nehmende Asylgesuch (vgl. Art. 13c Abs. 6 ANAG) rasch entschieden werden kann.
2.4 Nach dem Gesagten sind alle gesetzlichen Voraussetzungen für eine Haftverlängerung erfüllt. Die Verwaltungsgerichtsbeschwerde erweist sich als offensichtlich unbegründet und ist abzuweisen.
2.5 Entsprechend dem Verfahrensausgang wird der Beschwerdeführer grundsätzlich kostenpflichtig (Art. 156 Abs. 1 OG). In Fällen der vorliegenden Art rechtfertigt es sich jedoch, von der Erhebung einer Gerichtsgebühr abzusehen (Art. 154 und 153a Abs. 1 OG).
2.6 Das Kantonale Amt für Ausländerfragen Zug wird ersucht, dafür besorgt zu sein, dass das vorliegende Urteil dem Beschwerdeführer korrekt eröffnet und nötigenfalls verständlich gemacht wird.
2.7 Im Hinblick auf das Asylverfahren ist dem Bundesamt für Flüchtlinge eine Kopie der Verwaltungsgerichtsbeschwerde (einschliesslich Übersetzung) zur Kenntnis zu bringen.

Demnach erkennt das Bundesgericht
im Verfahren nach Art.36a OG:
im Verfahren nach Art.36a OG:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Es werden keine Kosten erhoben.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Ausländerfragen Zug und dem Verwaltungsgericht des Kantons Zug, Haftrichterin, sowie - zusammen mit einer Kopie der Beschwerdeschrift mitsamt Übersetzung - dem Bundesamt für Flüchtlinge schriftlich mitgeteilt.
Lausanne, 24. März 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: