Well, having been through this before my own wedding, I can tell you some of the things that are looked out for:
- Ketuba - this really functions as an attestation from a previous Beis Din that the person (or their mother or perhaps mother's mother) is Jewish.
- A Get would serve the same purpose, if the Ketuba wasn't available.
- A document attesting to conversion (sample here and here) for the person, (or their mother, etc.)
- A letter from a Rabbi attesting to the Jewishness of the person. Of course the Rabbi has to be a known quantity to the one doing the accepting, but this will generally substitute for the above three items.
In terms of how the Rabbi knows to write #4, this can come from reliable testimony from people who know the person. Here Jewish observance helps, in that if the person is observed behaving in a Torah observant manner over the course of several years, this can itself establish the presumption that the person is Jewish.
Another thing that can help is ancestral burial in a Jewish cemetery. There you have evidence that the cemetery operators believed the person to be Jewish.
In principle, as @yEz elaborated, a person's claim to be Jewish should be acceptable if there isn't anything to create the opposite presumption. However, since there are now people who are told they are Jewish when only their father is Jewish, or they have a conversion that isn't Halachically acceptable, this gets a lot murkier. Sure they may be telling the truth, it is just that "Jewish" doesn't mean what they think it means.