Halacha and the frum world take it for granted that whether a person is born Jewish is determined by whether he or she had a Jewish mother. It is assumed that the principle of matrilineal descent goes back as far as there have been Torah-abiding Jewish people. Yet we see in Tanach many examples of Jewish men marrying non-Jewish women. Yosef marries an Egyptian, Moshe a Mdianite, David a Pilishti, and so on. Their children are all considered Jewish. There is an assumption that these women were migayar, and in the case of Yosef and Osnas, a medrash that claims she was really Jewish all along, but there is no indication of this in the pesukim. There is also some indication in Tanach that a woman who married a non-Jewish man was then considered part of his nation, and their children were not Jewish.
The principle of matrilineal descent doesn't appear in any extra-biblical sources, either. Writers such as Philo of Alexandria and Josephus seem unaware of it, as do the Dead Sea scrolls and various early works which survive but were not canonized as part of Tanach. The earliest recorded instance of the principle of matrilineal descent seems to be in the mishnah.
The Mishnah in Kiddushin 3:12 discusses potential valid and invalid marriages, and states that in a halachically valid marriage, the status of the children is that of the father, i.e., whether the children are cohanim or not. When the marriage is invalid, the children are hallachically fatherless, and follow the status of the mother. A marriage between a Jew and non-Jew in not hallachically valid, so the children's Jewish status depends upon their mother's Jewish or non-Jewish status.
Under Roman law, a child is legally his father's heir only if he is the product of a valid legal marriage. Marriages recognized by the law were restricted to unions between Roman citizens. If a citizen married a non-citizen, the children followed the status of the mother. A Roman father and a non-Roman mother produced non-Roman children. A Roman mother and non-Roman father would theoretically produce Roman children, but a separate, later law dictated that the children follow the parent with the lower status.
The logic is identical to that found in the Mishnah. The Mishnah developed during the period when Judea was ruled by Rome. It seems more likely that the law of the powerful Roman Empire, which was legally binding throughout the empire, influenced Jewish jurors in the Roman province of Judea in the first centuries CE than that a hitherto unattested law from the backwater kingdom of Judah influenced Roman jurors hundreds of years earlier. It is likely, then, that matrilineal descent, the method by which we determine who is Jewish, is originally not a Torah principle but a Roman one. That something so fundamental to Jewish identity could have originated in another culture undermines the idea that Judaism as practiced today in the frum world is essentially the same as it has been down through the ages.
 The following discussion of matrilineal descent is based on Cohen, S.J.D. (2001). The Matrilineal Principle in Historical Perspective. AJS Review. Retrieved from http://www.jewishrecon.org/resource-files/files/Shaye%20Cohen%20-%20the%20Matrilineal%20Principle%20in%20Historical%20Perspective.pdf
 The author of the article provides another suggestion for the origin of matrilineal descent. He says that it may be part of the mishnah's fascination with categorizing things, and points to a discussion of kilayim, an animal such as a mule which is the offspring of two species. There is an opinion there that the species of the animal follows the mother, and so too, the author suggests, in cases of two nationalities the child follows the mother. I would suggest that it is more likely that his first explanation is correct, and matrilineal descent was borrowed from Roman law. The logic of the Roman law and of the Mishnah is identical, and given the historical timing of the Mishnah is probably not a coincidence. If so, then the principle of matrilineal descent with regard to children may have been applied to cases of kilayim, rather than the other way around.