The Gemara says (Yevamos 47a):
ת"ר מי שבא ואמר גר אני יכול נקבלנו ת"ל אתך במוחזק לך בא ועדיו עמו מנין ת"ל וכי יגור אתך גר בארצכם אין לי אלא בארץ בח"ל מנין תלמוד לומר אתך בכל מקום שאתך אם כן מה ת"ל בארץ בארץ צריך להביא ראיה בח"ל אין צריך להביא ראיה דברי ר' יהודה וחכמים אומרים בין בארץ בין בחוצה לארץ צריך להביא ראיה
The Sages taught in a baraita: With regard to someone who came and said: I am a convert, one might have thought that we should accept him; therefore, the verse states: “And if a convert sojourns with you in your land, you shall not oppress him” (Leviticus 19:33). The emphasis on “with you” suggests that only someone who was already presumed by you to be a valid convert should be accepted as a convert. If he came and brought witnesses to his conversion with him, from where is it derived that he is to be accepted? It is from the beginning of that verse, which states: “And if a convert sojourns with you in your land I have derived only that a convert is accepted in Eretz Yisrael; from where do I derive that also outside of Eretz Yisrael he is to be accepted? The verse states “with you,” which indicates that in any place that he is with you, you should accept him. If so, what is the meaning when the verse states: In the land? This indicates that in Eretz Yisrael he needs to bring evidence that he is a convert, but outside of Eretz Yisrael he does not need to bring evidence that he is a convert; rather, his claim is accepted. This is the statement of Rabbi Yehuda. And the Rabbis say: Whether he is in Eretz Yisrael or whether he is outside of Eretz Yisrael, he needs to bring evidence.
And the Rambam Issurei Biyah, 13:10 says:
אֲבָל מִי שֶׁבָּא וְאָמַר שֶׁהָיָה עַכּוּ"ם וְנִתְגַּיֵּר בְּבֵית דִּין נֶאֱמָן. שֶׁהַפֶּה שֶׁאָסַר הוּא הַפֶּה שֶׁהִתִּיר. בַּמֶּה דְּבָרִים אֲמוּרִים בְּאֶרֶץ יִשְׂרָאֵל וּבְאוֹתָן הַיָּמִים שֶׁחֶזְקַת הַכּל שָׁם בְּחֶזְקַת יִשְׂרָאֵל. אֲבָל בְּחוּצָה לָאָרֶץ צָרִיךְ לְהָבִיא רְאָיָה וְאַחַר כָּךְ יִשָּׂא יִשְׂרְאֵלִית. וַאֲנִי אוֹמֵר שֶׁזּוֹ מַעֲלָה בְּיוּחֲסִין:
Someone who comes and says that he was a non-Jew and converted in court, he's believed, as the same mouth which said that he's forbidden said that he's permitted. When is this true? In Israel in the time when the assumption was that everyone is Jewish. However, outside of Israel he has to bring proof and only then marry, and I say that this is because Yuchsin is strict.
Practically, there are a few Vaads which provides a service to prove Judaism.