What qualifies one to be a Jew both ethnically and religiously? Has it always been so? (From Jacob/Israel to now). The Old Testament (in part) uses a patriarchal (the male side) genealogy to substantiate parentage. Paul of Tarsus was considered a Jew , yet had a non-Jew parent [Editors note: this is not clear- the only source is apparently the Greek Scriptures, and Paul's writings which can be questioned. It is possible either that Paul's parents converted, or that Paul did. Tarsus was a very non-Jewish area]. I've read that a Jewish mother qualifies the children as Jewish for religious purposes. Please edify me as regards this topic.

There are several permutations to your important question: defining "ethnic" vs. "religious" Judaism, from both historical and contemporary perspectives. While the term of "religious" can be ambiguous, I will define it here as being "Jewish" in accordance with Jewish law as opposed to "ethnic" Judaism which would have implications for social integration or personal identification.  
The distinction between "religious" and "ethnic" Judaism exists in certain parts of our history, though not in others. Before the Torah was given, Jacob's son Judah married an unnamed Cannanite woman only known as the daughter of Shua (Gen. 38:2), and the while the children of this marriage 'Er and Onan died, they were still recognized as being Judah's children (Gen. 46:12). Joseph's children Menashen and Ephraim were born from an Egyptian woman (Gen. 41:50), yet merited a special blessing from Jacob and were treated as "tribes" in their own right (Gen. 48).  In these examples, the "Jewishness" was determined by the father, but predating the giving of the Torah, it may make more sense to view this Jewishness as more "ethnic" than "religious" as it pertains more to familial attachments.
Since at least the times of the Mishnah (M. Kiddushin 3:12), religious Jewishness was defined as someone being born of a Jewish mother, or having converted in accordance with Jewish Law.  This definition has endured for millennia such modern reformations to define Jewishness based on the father's status were met with harsh criticism. During this extensive period, I would suggest the division between ethnic and religious Judaism was not nearly as pronounced nor as relevant as it is today, mostly because Jewish law only recognizes halakhic Jewishness, not ethnic Jewishness. (Note that this distinction is only meaningful when there is a conflict between the two).  Depending on the location and century, outside forces such as governmental segregationist policies contributed towards the conflation of ethnicity and religion. 
We are probably more familiar with the ethnic/religious dichotomy as it pertains to contemporary identity, and this is where there is much personal confusion. Once Jews gained the freedom to assimilate, being "Jewish" became more of a conscious decision. Therefore it is not as unusual to find someone claiming to be Jewish based on personal identity rather than meeting halakhic criteria. However, personal Judaism may not even be classifiable as "ethnic" Judaism if membership is conditional on communal acceptance. If we view Judaism as a purely social phenomenon, then acceptance into the tribe would be predicated on other members of the "tribe" validating an individual's identity.  This is a much harder question to answer historically given that we are limited by the data available. Even if we can produce evidence of one group accepting another's Jewishness we cannot be assured other group would not have rejected an individual. Not being a historian, I cannot responsibly offer any speculations in this regard for any time period.
Today we can easily identify which groups accept and reject which definitions of Jewishness, both in terms of ethnicity, identity, or Jewish law. For obvious reasons, this fundamental question of identity and belonging remain highly contentious.
 

Dear friend,

The answer to the question you ask is actually fairly simple: a person is a Jew if their mother is Jewish, or if they undergo conversion via immersion in a mikvah if female, and immersion in a mikvah plus circumcision for the sake of conversion if male (if the man is already circumcised, there is a procedure called hatafat dam brit which draws a drop of blood instead). The prospective convert comes before a panel of rabbis who ask them questions, and then when they are satisfied, the person undergoes the procedures I mention above.
That is really all there is to it.

Reputable rabbis will also ask the prospective convert to undergo some period of learning prior to the beit din (the panel of rabbis) about what it means to be Jewish and what the person's obligations will be once they have converted, so that they know ahead of time what will be required of them for the rest of their life.
That said, this clearly has not always been the case historically speaking: it is clear that in the biblical era, being Jewish was passed along via the father: this is no longer the case. The reasons for this change are unclear (although heavily speculated upon), but also essentially irrelevant - Judaism is a rabbinic religion: we follow the laws of Judaism as explicated and interpreted by the rabbis.

Nevertheless, Judaism is opposed to intermarriage, and always has been.

There are certain beliefs which a Jew may not hold - for example, a Jew who professes belief in the divine Being taking material form would be considered a sinner by Judaism. In a family where one parent holds a belief that a Jewish person is not permitted to hold, it  would be very difficult to teach that to one's children - indeed, it would be unfair to the non-Jewish parent. For "ethnic purposes" (as you say - I love your phrasing) the person would be Jewish, but for "religious purposes," -no. One cannot, for example, call to the Torah a person who is known to hold such a belief, although they remain fully Jewish. -It is a bit complicated in that sense.
If this person who had a Jewish mother was taught what it means to be Jewish and decided to affiliate themselves with the obligations and beliefs of Judaism, however, there is no need to convert - they are fully Jewish.

Sometime ago I had the privilege of responding to a very similar query. I believe that response (below) may serve as an entry point to this discussion.

 

Few topics generate more controversy for the “organized” Jewish community – misplaced energy or not, by which I mean, there may be more pressing challenges to and in Jewish life – than the matter of who is or is not a Jew.

 

While all authorities likely would agree only that the argument is about a minimalist criterion for inclusion in the community, that does not diminish the intensity of the different positions, even as the points of view are an expression of the integrity of the various movements (Orthodox, Conservative, etc.) themselves.

 

The present writer, as part of the Reform community, has long subscribed to the insistence that biology is not destiny, meaning that conviction and commitment are essential elements to a genuine embrace of a religious, tribal or ethnic identity. That said, our community accepts persons who have (at least) one Jewish parent (mother or father) and, here the crucial part, choose to live as Jews. Nonetheless, with regard to individuals who will be perceived by others as not legitimately Jewish (i.e. patrilineal descent only), we encourage them to recognize that as a reality, one that comes with no shortage of challenges.

 

In some cases, therefore, individuals who understand themselves as already belonging to Jewish life may choose to have a conversion ceremony, albeit the auspices under which that is undertaken are another one of the controversies that are a too prominent part of the contemporary Jewish scene.

 

To the question at hand, then, Reform Judaism acknowledges as a legitimate part of Jewish life someone who has at least one Jewish parent and chooses to live as a Jew. or, equally, an individual who converts to Judaism.

 

Rabbi Michael Zedek