UPDATE:
There are various batei din around the world who will do a "birur yahadut," an investigation, and then issue you a "Teudat Yahadut" or a "Teudat Ravakut" or an "Ishur Yahadut." They will tell you exactly what you need. The RCA for example asks for this:
Copies of passport, birth certificate, driver's license, teudat zehut
(if you are Israeli); passport photo; family tree going back at least
3 generations with as many details as possible; mother's birth
certficate; letter from a rabbi confirming you are jewish; parents'
ketubah; any other documents (including diploma from jewish day
school, grandparents' burial records from jewish cemetery, letters
from family members describing jewish practices).
(I was told that census records and even pictures of your ancestors may also carry some weight, though I'm not sure how much.)
The Sydney Beth Din asks for:
Copies of birth certificate, mother's birth certificate, driver's
license, parents' ketubah, parents' marriage certificate, and get or
death records in case of remarriage; affirmation that you are Jewish
by 2 Jewish people not related to you nor 2 each other.
It is not exactly clear from the above how much you need for a proof. However, in my experience, it seems you need either one Orthodox religious document from the maternal line (=ketubah/get/conversion certificate/record of burial in an Orthodox cemetery), or two letters from Orthodox rabbis attesting that you are Jewish. However, I was asked for more, and it seems some people are asked for less.
For practical purposes, it may be best to contact a local beis din and try to get a teudat yahadut from them; if this fails, you can then try in higher batei din. If all that fails, you may need a giur l'chumra or even a giur.