Art. 13b Abs. 2 ANAG, hat sich ergeben:
A.- Der 1975 geborene X._ stammt gemäss eigenen Angaben aus der Ukraine und reiste am Morgen des 21. Oktober 2001 von Österreich kommend zu Fuss illegal über die Grenze in die Schweiz ein. Am Abend des 21. Oktober 2001 nahm die Kantonspolizei ihn und seine Begleiter in einem Industrie- und Bürogebäude in St. Margrethen fest. Mit Strafbescheid vom 23. November 2001 verurteilte ihn das Untersuchungsamt Altstätten wegen mehrfachen Diebstahls und Versuchs dazu, mehrfacher Sachbeschädigung, mehrfachen Hausfriedensbruchs sowie rechtswidriger Einreise und rechtswidrigen Aufenthalts zu drei Monaten Gefängnis bedingt, abzüglich 35 Tage Untersuchungshaft.
Ebenfalls am 23. November 2001 wies das Ausländeramt des Kantons St. Gallen X._ formlos aus dem Gebiet der Schweiz weg und ordnete über ihn die Ausschaffungshaft an. Mit Entscheid vom 27. November 2001 genehmigte der Einzelrichter der Verwaltungsrekurskommission des Kantons St. Gallen die Ausschaffungshaft bis zum 22. Februar 2002. Mit Entscheid vom 19. Februar 2002 verlängerte er die Haft bis zum 21. Mai 2002.
B.- Dagegen hat X._ mit Eingabe vom 4. März 2002 beim Bundesgericht Verwaltungsgerichtsbeschwerde erhoben. Er beantragt, den Entscheid der Verwaltungsrekurskommission vom 19. Februar 2002 aufzuheben und ihn aus der Ausschaffungshaft zu entlassen. Zudem ersucht er um unentgeltliche Rechtspflege und Verbeiständung.
Das Ausländeramt und die Verwaltungsrekurskommission des Kantons St. Gallen beantragen die Abweisung der Beschwerde. Der Beschwerdeführer hat sich nicht mehr zur Sache geäussert. Das Bundesamt für Ausländerfragen hat sich nicht vernehmen lassen.

Das Bundesgericht zieht in Erwägung:
1.- Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen, wenn die Voraussetzungen von Art. 13b des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) erfüllt sind.
Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger, Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2a S. 61), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist. Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (<ref-ruling> E. 1 S. 3), die Ausschaffung rechtlich und tatsächlich möglich sein (Art. 13c Abs. 5 lit. a ANAG; vgl. <ref-ruling> E. 3 S. 152 ff.) und die Papierbeschaffung mit dem nötigen Nachdruck verfolgt werden (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; <ref-ruling> ff.). Die Haft darf höchstens drei Monate dauern; stehen dem Vollzug der Wegweisung 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).
2.- Das Ausländeramt des Kantons St. Gallen hat den Beschwerdeführer am 23. November 2001 formlos aus dem Gebiet der Schweiz weggewiesen. Der Vollzug dieser Wegweisung ist zurzeit wegen fehlender Reisepapiere noch nicht möglich, jedoch absehbar. Dem Vollzug stehen insoweit besondere Hindernisse entgegen, als die Identität des Beschwerdeführers nach wie vor nicht restlos geklärt ist. Nachdem der Beschwerdeführer wegen der Beteiligung an einem Einbruchdiebstahl verurteilt worden ist und zudem in Deutschland unter einem andern Namen aufgetreten war, ist der Haftgrund der Untertauchensgefahr ohne Weiteres gegeben. Dafür, dass der Vollzug der Ausschaffung rechtlich oder tatsächlich unmöglich sein sollte, bestehen vorderhand keine Anhaltspunkte.
3.- Fraglich ist hingegen, ob sich die Behörden an das Beschleunigungsgebot gehalten haben.
a) Nach Art. 13b Abs. 3 ANAG sind die für den Vollzug der Weg- oder Ausweisung nötigen Vorkehrungen umgehend zu treffen. Arbeitet die zuständige Behörde nicht zielstrebig auf den Wegweisungsvollzug hin, ist die Ausschaffungshaft mit der einzig zulässigen Zielsetzung des Zwangsmassnahmengesetzes, nämlich die Ausschaffung des Ausländers sicherzustellen, nicht mehr vereinbar. Sie verstösst in diesem Fall gegen Art. 5 Ziff. 1 lit. f EMRK, weil das Ausweisungsverfahren nicht mehr als "schwebend" im Sinne dieser Bestimmung gelten kann. Die Pflicht, Vorbereitungen für den Vollzug der Ausschaffung zu treffen, beginnt nicht erst mit der Anordnung der fremdenpolizeilichen Haft. Befindet sich ein Ausländer etwa in Untersuchungshaft oder im Strafvollzug, müssen bei klarer fremdenpolizeilicher Ausgangslage bereits während dieser Zeit Abklärungen mit Blick auf die Ausschaffung eingeleitet werden. Die Strafvollzugs- und Fremdenpolizeibehörden haben hierfür nötigenfalls zusammenzuarbeiten; welche der beiden allfällige Verzögerungen zu vertreten hat, ist bei der Beurteilung der Einhaltung des Beschleunigungsgebotes unerheblich. Die Vollzugsbehörden dürfen nicht untätig bleiben. Sie müssen versuchen, die Identität des Ausländers festzustellen und die für seine Ausschaffung erforderlichen Papiere auch ohne seine Mitwirkung zu beschaffen. Ob das Beschleunigungsgebot verletzt wurde, ist nach den Umständen des Einzelfalles zu beurteilen.
Dabei kann ein widersprüchliches Verhalten des Betroffenen mitberücksichtigt werden. Das Bundesgericht hat eine Verletzung des Beschleunigungsgebotes bejaht, wenn während rund zwei Monaten keinerlei Vorkehren mehr im Hinblick auf die Ausschaffung getroffen wurden, ohne dass die Verzögerung in erster Linie auf das Verhalten ausländischer Behörden oder des Betroffenen selber zurückging (<ref-ruling> E. 3a S. 50 f., mit Hinweisen).
Das Beschleunigungsgebot gebietet es den Behörden - und zwar sowohl den kantonalen als auch den Bundesbehör- den -, zu versuchen, so schnell wie möglich die Identität des Ausländers festzustellen und die für seine Ausschaffung erforderlichen Papiere zu beschaffen. Alle zur Verfügung stehenden Massnahmen sind zu ergreifen, die geeignet erscheinen, den Vollzug der Ausschaffung zu beschleunigen.
Die Kantone können bei den Bundesbehörden um Vollzugsunterstützung ersuchen (vgl. Verordnung vom 11. August 1999 über den Vollzug der Weg- und Ausweisung von ausländischen Personen [VVWA; SR 142. 281]):
Gemäss Art. 1 Abs. 1 VVWA richtet das Eidgenössische Justiz- und Polizeidepartement eine Fachabteilung für Vollzugsunterstützung (Fachabteilung) ein. Sie ist dem Bundesamt für Flüchtlinge (Bundesamt) unterstellt. Die Fachabteilung beschafft Reisepapiere für weg- und ausgewiesene ausländische Personen auf Gesuch der zuständigen kantonalen Fremdenpolizeibehörde hin (Art. 2 Abs. 1 VVWA). Sie ist Ansprechpartnerin der heimatlichen Behörden, insbesondere der diplomatisch-konsularischen Vertretungen der Heimat- oder Herkunftsstaaten von weg- und ausgewiesenen ausländischen Personen, sofern nicht im Rahmen eines Rückübernahmeabkommens oder in Absprache mit den Kantonen etwas anderes bestimmt wurde (Art. 2 Abs. 2 VVWA). Die Fachabteilung überprüft im Rahmen der Reisepapierbeschaffung die Identität und die Staatsangehörigkeit von weg- und ausgewiesenen ausländischen Personen. Sie kann zu diesem Zweck insbesondere Interviews, Vorführungen bei den heimatlichen Vertretungen sowie Sprach- oder Textanalysen durchführen. Sie orientiert den Kanton über das Ergebnis ihrer Abklärung (Art. 3 Abs. 1 und 2VVWA).
b) Während der rund einen Monat dauernden Untersuchungshaft wurden, soweit aus den Akten ersichtlich, keine Abklärungen zur Identität des Beschwerdeführers getroffen.
Ob die Strafvollzugsbehörden gemeinsam mit den Fremdenpolizeibehörden schon in dieser Phase derartige Abklärungen hätten in die Wege leiten müssen, kann im vorliegenden Fall offen bleiben, da hier - wie im Folgenden aufzuzeigen ist - das Beschleunigungsgebot auch als verletzt gelten muss, wenn einzig der Zeitraum ab Anordnung der Ausschaffungshaft bis zum angefochtenen Haftverlängerungsentscheid berücksichtigt wird.
c) Nach der Beendigung der Untersuchungshaft wurden die Behörden des Kantons St. Gallen vorerst umgehend tätig:
schon am 23. November 2001, am Tag der Anordnung der Ausschaffungshaft, ersuchte das Ausländeramt den Bund um Vollzugsunterstützung.
Am 26. November 2001 ersuchte die Kantonspolizei St. Gallen die österreichischen Behörden um Rückübernahme des Beschwerdeführers. Nachdem der Haftrichter die Anordnung der Ausschaffungshaft am 27. November 2001 genehmigt hatte, wiederholte das Ausländeramt mit Schreiben vom 29. November 2001 sein Begehren um Vollzugsunterstüt- zung. Am 28. November 2001 teilte die Sicherheitsdirektion für das Bundesland Vorarlberg der Kantonspolizei mit, dem Ersuchen um Rückübernahme könne nicht stattgegeben werden.
Am 3. Dezember 2001 teilte das - ebenfalls um Rückübernahme des Beschwerdeführers ersuchte - Bundesgrenzschutzamt Weil am Rhein mit, einer Rückübernahme könne nicht zugestimmt werden. Es fügte bei, der Beschwerdeführer sei am 12. Mai 2001 nach Deutschland eingereist und habe am 27. Juli 2001 in Leipzig einen Asylantrag gestellt, der abgelehnt worden sei.
Rund eineinhalb Monate später, am 16. Januar 2002, forderte die Kantonspolizei den Beschwerdeführer offenbar auf, sich telefonisch mit der Ukraine in Verbindung zu setzen. Mit Schreiben vom 22. Januar 2002 ersuchte das Ausländeramt des Kantons St. Gallen die Kantonspolizei, über die Identität des Beschwerdeführers Interpol-Abklärungen für die Länder Polen, Slowakei und Tschechien in die Wege zu leiten. Mit Schreiben vom 24. Januar 2002 teilte das Justiz- und Polizeidepartement dem Ausländeramt - in Bezugnahme auf ein Telefonat vom 15. Januar 2002 - mit, es habe betreffend den Beschwerdeführer Daktyvergleiche in Deutschland und Österreich eingeleitet; bisher verfüge es einzig über einen Antrag des Regierungspräsidiums Chemnitz um ein Ersatzreisepapier für einen Y._, der abschlägig beantwortet worden sei. Am 31. Januar 2001 ersuchte die Kantonspolizei St. Gallen das Bundesamt für Polizei um Interpol-Abklärungen in Polen, Tschechien und der Slowakei.
d) Nachdem am 3. Dezember 2001 bekannt geworden war, dass neben Österreich auch Deutschland nicht bereit war, den Beschwerdeführer zu übernehmen, geschah seitens der Behörden - abgesehen von den Daktyvergleichen in Deutschland und Österreich, von denen nicht genau bekannt ist, ob das Eidgenössische Justiz- und Polizeidepartement sie vor oder nach dem Telefongespräch vom 15. Januar 2002 mit dem Ausländeramt eingeleitet hat - während der eineinhalb Monate bis zu diesem Telefongespräch nichts.
Zu beanstanden ist dabei vor allem, dass in dieser Phase keine Kontaktnahme mit den ukrainischen Behörden stattgefunden hat. Dies erstaunt umso mehr, als der Beschwerdeführer schon am 26. Oktober 2001 gegenüber der Kantonspolizei erklärt hatte, aus der Ukraine zu stammen.
Die ukrainischen Behörden wurden auch in der Folge, soweit aus den Akten ersichtlich, bis zum Zeitpunkt des angefochtenen Haftverlängerungsentscheids nicht kontaktiert.
Die Aufforderung der Kantonspolizei vom 16. Januar 2002 an den Beschwerdeführer, sich mit der Ukraine telefonisch in Verbindung zu setzen, ist zwar nicht von vornherein untauglich; sie ersetzt aber die Kontaktnahme seitens der Behörden mit dem angeblichen Herkunftsstaat des Ausländers in keiner Weise; dasselbe gilt für das am 31. Januar 2002 ergangene Ersuchen der Kantonspolizei an das Bundesamt für Polizei um Einleitung von Interpol-Abklärungen betreffend Polen, Tschechien und der Slowakei.
Eine erste Anfrage an die Behörden des Landes, aus dem der Beschwerdeführer zu stammen behauptet, hätte umgehend nach der Anordnung der Ausschaffungshaft stattfinden sollen, spätestens aber nach dem 3. Dezember 2001, als klar war, dass weder Deutschland noch Österreich bereit waren, den Beschwerdeführer zurückzunehmen. Da eine solche Anfrage nicht stattgefunden hat, wiegt die Untätigkeit der Behörden während der folgenden eineinhalb Monate umso schwerer. Eine solche Situation ist insbesondere nicht zu vergleichen mit einem Fall, wo die in Frage kommenden Herkunftsstaaten schon angegangen worden sind, sich jedoch mit der Antwort Zeit lassen: Diesfalls bleibt den kantonalen bzw. den Bundesbehörden nichts anderes übrig als abzuwarten und allenfalls von Zeit zu Zeit bei den ausländischen Vertretungen "nachzudoppeln".
Die oben ausgeführte Rechtsprechung des Bundesgerichts, wonach eine Verletzung des Beschleunigungsgebots bejaht wird, wenn während rund zwei Monaten keine Vorkehren mehr im Hinblick auf die Ausschaffung getroffen wurden, ohne dass die Verzögerung in erster Linie auf das Verhalten ausländischer Behörden oder des Betroffenen selber zurückging (<ref-ruling> E. 2a S. 51), ist nicht als Freibrief dafür zu verstehen, nach Anordnung der Ausschaffungshaft während der Dauer von knapp unter zwei Monaten entweder gar nichts zu unternehmen oder zwar ein paar Abklärungen zu treffen, hingegen die erfolgversprechendsten Vorkehren vorerst zu unterlassen. Gerade die bekannte Tatsache, dass die ausländischen Behörden sich oft mit einer Antwort Zeit lassen, gebietet um so mehr, so schnell als möglich an sie zu gelangen, da sonst viel Zeit ungenutzt verstreicht und das Risiko steigt, dass der Ausländer innerhalb der maximal zulässigen Haftdauer von neun Monaten nicht ausgeschafft werden kann.
e) Zusammenfassend ist festzuhalten, dass im vorliegenden Fall die für den Vollzug der Wegweisung notwendigen Massnahmen nicht umgehend an die Hand genommen worden sind und das Beschleunigungsgebot daher als verletzt zu gelten hat. Dabei steht nicht etwa das völlige Untätigsein der Behörden während der sechs Wochen zwischen dem 3. Dezember 2001 und dem 15. Januar 2002 im Vordergrund, sondern vielmehr die Tatsache, dass, soweit aktenkundig, während der gesamten ersten drei Monate der Ausschaffungshaft diejenige Massnahme, die sich am ersten aufgedrängt hätte - eine Kontaktnahme mit den ukrainischen Behörden - überhaupt unterblieben ist.
Nachdem die kantonalen Behörden sofort nach Anordnung der Ausschaffungshaft den Bund um Vollzugsunterstützung ersucht hatten, ist die Unterlassung der Kontaktnahme mit der ukrainischen Vertretung wohl hauptsächlich der Fachabteilung für Vollzugsunterstützung anzulasten. Nachdem die Verordnung über den Vollzug der Weg- und Ausweisung von ausländischen Personen ausdrücklich diese Fachabteilung als Ansprechpartnerin der diplomatisch-konsularischen Vertretungen der Heimat- und Herkunftsstaaten weggewiesener Ausländer bezeichnet - soweit nicht im Rahmen eines Rückübernahmeübereinkommens oder in Absprache mit den Kantonen etwas anderes bestimmt wurde - (Art. 2 Abs. 2 VVWA), kann den kantonalen Behörden kaum ein Vorwurf daraus gemacht werden, dass sie die Kontaktnahme mit der ukrainischen Vertretung nicht selber an die Hand genommen, sondern im Vertrauen auf das Tätigwerden der von ihnen angegangenen Fachabteilung unterlassen haben.
Die Frage, welche Aufgaben im Zusammenhang mit Identitätsabklärungen und Beschaffung von Reisepapieren den kantonalen und welche den Bundesbehörden obliegen, braucht aber hier nicht endgültig geklärt zu werden, da die Kontaktnahme mit der ukrainischen Vertretung bis zum Zeitpunkt des Haftverlängerungsentscheids weder seitens der kantonalen Behörden noch seitens der Fachabteilung erfolgt ist; das Beschleunigungsgebot ist auf jeden Fall verletzt.
4.- a) Die Verletzung des Beschleunigungsgebots muss in der Regel zur Haftentlassung führen, wie das Bundesgericht bereits zur altrechtlichen Internierung entschieden hat. In der Tat lässt sich dann, wenn die zuständigen Behörden den Ausschaffungsvollzug nicht gehörig vorangetrieben haben, nicht mehr von einem hängigen Ausweisungsverfahren im Sinne von Art. 5 Ziff. 1 lit. f EMRK sprechen (vgl. <ref-ruling> E. 3 S. 206 f; 423 E. 4 S. 425 ff.). Die Haft dient dann nicht mehr dem einzigen vom Gesetz vorgesehenen Zweck, den Vollzug der Wegweisung sicherzustellen. Der Festhaltung des Beschwerdeführers in der Ausschaffungshaft fehlt somit die gesetzliche Grundlage.
Die vorliegende Beschwerde ist daher vollumfänglich gutzuheissen, der angefochtene Entscheid aufzuheben und der Beschwerdeführer unverzüglich aus der Haft zu entlassen.
b) Das Ausländeramt des Kantons St. Gallen hat dem Bundesgericht mit Fax vom 18. März 2002 ein Schreiben des Bundesamts für Flüchtlinge vom 15. März 2002 weitergeleitet, aus dem hervorgeht, dass inzwischen am 12. März 2002 eine Befragung des Beschwerdeführers durch den Vertreter des ukrainischen Konsulats in Bern stattgefunden hat; das Bundesamt für Flüchtlinge hat zudem Nachforschungen über die Schweizerische Vertretung in Kiev angekündigt. Für den folgenden Zeitraum bis zur Beschaffung von Reisepapieren für den Beschwerdeführer steht es den kantonalen Behörden frei, diesen zu verpflichten, sich für weitere Abklärungen zur Verfügung zu halten, und allenfalls die Ein- oder Ausgrenzung des Beschwerdeführers gemäss Art. 13e ANAG zu prüfen.
Der Ausländer, der entsprechende Anordnungen missachtet, wird mit Gefängnis bis zu einem Jahr oder mit Haft bestraft, falls sich der Vollzug der Weg- oder Ausweisung aus rechtlichen oder tatsächlichen Gründen als undurchführbar erweist (Art. 23a ANAG). Ist dies nicht der Fall, kann er möglicherweise gestützt auf Art. 13b Abs. 1 lit. b (in Verbindung mit Art. 13a lit. b ANAG) erneut in Ausschaffungshaft genommen werden.
5.- Entsprechend dem Verfahrensausgang ist keine Gerichtsgebühr zu erheben (Art. 156 Abs. 2 OG). Zudem hat der Kanton St. Gallen dem Beschwerdeführer die durch den Rechtsstreit verursachten notwendigen Kosten zu ersetzen (Art. 159 Abs. 2 OG). Damit wird das Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird gutgeheissen und der Entscheid des Einzelrichters der Verwaltungsrekurskommission des Kantons St. Gallen vom 19. Februar 2002 aufgehoben.
2.- Der Beschwerdeführer ist ohne Verzug aus der Haft zu entlassen.
3.- Es werden keine Kosten erhoben.
4.- Der Kanton St. Gallen hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
5.- Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos erklärt.
6.- Dieses Urteil wird dem Beschwerdeführer, dem Ausländeramt und der Verwaltungsrekurskommission (Zwangsmassnahmen im Ausländerrecht) des Kantons St. Gallen sowie dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 19. März 2002
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident: Die Gerichtsschreiberin: