If a Karaite who knows that his mother is Jewish (Karaite) wanted to join the Orthodox Jewish Community - would he be required to undergo a conversion?
Rema (Even Haezer 4:37, citing Beis Yosef) says of the Karaites "they are all possible mamzerim, and they should not be accepted if they want to return [to Rabbanite Judaism]." (Interestingly, Rambam, Hil. Mamrim 3:3, seems to disagree: he advocates trying to help them do teshuvah.)
It seems that there is some dispute about this nowadays, though. This Wikipedia article mentions the views of R. Eliyahu Bakshi-Doron, R. Ovadiah Yosef and others as encouraging marriages between Karaites and Rabbanite Jews, though it also mentions unnamed "Ashkenazi Haredi scholars" who consider them non-Jews and would require their conversion (though of course this would also dispose of the "possible mamzerus" issue).
A Jew does not convert when allegiances are switched within the various Jewish movements. A Karaite Jew with a Karaite Jewish mother will have no problems becoming an Orthodox Jew if he seeks to observe as a Sephardic Orthodox Jew. This statement is made on the basis of a statement by the Orthodox Sephardic Chief Rabbi of Netanya, Rabbi David Chelouche, who in an article in the Jerusalem Post entitled "Laying Down the Oral Law" on May 22, 2007 said: "Rabbi David Chayim Chelouche, the chief rabbi of Netanya, agrees. "A Karaite is a Jew," says Chelouche, who has written a great deal about the Karaites. "We accept them as Jews and every one of them who wishes to come back [to mainstream Judaism] we accept back. (There was once a question about whether Karaites needed to undergo a token circumcision in order to switch to rabbinic Judaism, but the rabbinate agrees today that it is not necessary.) He cautions, however, that the acceptance of Karaites as Jews should not be confused with acceptance of their practice of excluding the Oral Law. "A person cannot make his own Torah," he says.
They are largely intermarried, so I think they would likely need to convert.
However, everything they do for lifecycle events is invalid in Halachah. Therefore, it is just as easy to speculate that the vast majority of those from an uninterrupted Jewish line (without conversion) are Mamzerim, as it is that the vast majority of those who come from anyone who converted under Karaite processes is not Halachically Jewish.
It would be nearly impossible to determine the lineage of anyone, and even a just-in-case conversion might therefore be iffy, though I'm no expert.
It seems according to the Radvaz 1:73 that a man who wants to marry a Jewish woman who was previously a karaite and now accepts all the derabbanans is allowed. He held that their(karaites) kiddushin is not a kiddushin at all and the problem of mamzerut does not apply.
He ends off saying that in Egypt they had a mass conversion of Karaites and they were known to have very good yichus and even more so the chashuv families married into their families.
I recently had a discussion with several Orthodox rabbis about what would be required for them to be comfortable performing a wedding between a Rabbanite and a Karaite. In addition to checking to make sure that the Karaite individual was Karaite Jewish for several generations, none of them seemed to require anything amounting to a conversion. At least one required that the karaite individual accept certain rabbinic Halakha.
The implication seems to be that at least some Orthodox Rabbanites view Karaites (with Karaite lineage) to be Jews, but that (in the rabbinic opinion) Karaites are on the wrong path. In the old days this was called heresy. Implicit in the term heretic, though, is that the individuals is a member of the community, but that the individual holds views that are not commonly accepted. The fact that Karaites were called heretics implies that they were viewed to be Jewish.
I used to serve on the board of directors for the Karaite Jewish University. At that time (several years ago), the Karaite position was that any Jew from any movement can become a karaite without conversion. Of course, Karaites and Rabbanites historically differed on what made someone Jewish (Matrilineal v. Patrilineal). But that is a topic for a different day.