Other than declaring him "made of the seed of David according to the flesh" (Romans 1:3) and "born of a woman" (Galatians 4:4) Paul tells us nothing about the parentage of Jesus.
One wonders why Paul would tell us that Jesus was born of a woman without mentioning his mother's name. It's kind of like telling us Jesus had two arms and two legs. Why insist that Jesus was "born of a woman" unless there were people who said that he wasn't? Why insist that Jesus was made "according to the flesh" if he was known to be an actual historical person? The only reason Paul has for stating this is to counter claims during his time that Jesus didn't come in the flesh.
Jesus's mother doesn't get named the first time she's mentioned in the Gospels either:
There came then his brethren and his mother, and, standing without, sent unto him, calling him. And the multitude sat about him, and they said unto him, Behold, thy mother and thy brethren without seek for thee. And he answered them, saying, Who is my mother, or my brethren? And he looked round about on them which sat about him, and said, Behold my mother and my brethren! (Mark 3:31-34)
Here, Jesus seems to be disowning his biological family in order to make his followers his new family. It's interesting to note that Mary doesn't appear at the crucifixion or at the tomb of Jesus in Mark. The only other time Mark mentions her he implies that she disowned Jesus:
Is not this the carpenter, the son of Mary, the brother of James, and Joses, and of Juda, and Simon? and are not his sisters here with us? And they were offended at him. But Jesus, said unto them, A prophet is not without honour, but in his own country, and among his own kin, and in his own house. (Mark 6:3-4)
Jesus tells his followers he is without honor among his own kin. If we only read Paul and Mark, the only thing we know about Jesus's family is that he didn't get along with them. Mark has no birth story and no mention of who the father of Jesus was. In fact, Mark implies that Jesus was an illegitimate child by calling him "the son of Mary". During this time, men were always called the son of their father even if their father was dead. The only time they were called the son of their mother was if it was unknown who their father was.
The Gospel of John also implies that Jesus was a bastard:
I speak that which I have seen with my Father: and ye do that which ye have seen with your father.
They answered and said unto him, Abraham is our father.
Jesus saith unto them, If ye were Abraham's children, ye would do the works of Abraham. But now ye seek to kill me, a man that hath told you the truth, which I have heard of God: this did not Abraham. Ye do the deeds of your father.
Then said they to him, We be not born of fornication; we have one Father, even God. (John 8:38-41)
Many scholars agree that the Jew's reply to Jesus that "We be not born in fornication" implies that Jesus was.
However, unlike Mark, John does call Jesus "the son of Joseph", but only in passing (John 1:45, John 6:42). John also contains no birth narrative however, so we have no information about the father of Jesus except his name.
Matthew and Luke
The only time Joseph is mentioned in Matthew and Luke are in the birth narratives and when Jesus is taken to Jerusalem at the age of twelve.
Mark says that Jesus is a carpenter. Matthew changes this to Jesus being the son of a carpenter:
Is not this the carpenter's son? is not his mother called Mary? and his brethren, James, and Joses, and Simon, and Judas? And his sisters, are they not all with us? Whence then hath this man all these things? And they were offended in him. But Jesus said unto them, A prophet is not without honour, save in his own country, and in his own house. (Matthew 13:55-57)
The reason Matthew changes Jesus from a carpenter into a son of a carpenter is to avoid calling him "the son of Mary" like Mark does. Matthew wants Jesus to seem legitimate.
In his first chapter, Matthew gives a genealogy for Joseph, the "father" of Jesus which is completely different from the genealogy given in Luke. Jewish genealogies usually just list the male ancestors, but for some reason, Matthew includes four women. The women Matthew choses to include are all of ill repute. These women are Tamar (or Thamar), Rachab (or Rahab), Ruth, and Bathsheba.
Judah (or Judas) married his firstborn son Er to Tamar, but God killed Er for being wicked. Judah then had his son Onan marry Tamar, but Onan refused to get her pregnant, so God slew him as well. Judah didn't want any more of his sons to be killed, so he refused to marry any more of them to Tamar. In order to become pregnant, Tamar then dressed up like a prostitute and seduced her father-in-law (Genesis 38:6-30).
Rahab was a prostitute who lived in Jericho who helped the Israelites destroy her city (Joshua 2:1-24). Ruth was a Moabite, an enemy of Israel, yet she married a Judaean and had a close (some might say lesbian) relationship with her mother-in-law Naomi. (The Book of Ruth) Bathsheba was the wife of Uriah the Hittie who was seduced and impregnated by King David. When David discovered Bathsheba was pregnant, he sent Uriah into battle with orders that he should be killed. Bathsheba later became the mother of Solomon. (2 Samuel 11:1-27)
Why does Matthew include a prostitute, two women who got pregnant out of wedlock, and a possible lesbian in the genealogy of Jesus? He seems to be pointing out that just because these women weren't sexually pure doesn't mean their sons were tainted. The reasoning seems to be that since Solomon and other great Jewish heroes had mothers who weren't sexually pure, it's OK that the mother of Jesus wasn't sexually pure either.
Joseph may not have been Jesus's real dad, but what do we know about him? Mark and Paul don't mention him at all and John only gives us his name. How about Matthew and Luke?
Matthew seems to have based his Joseph on Joseph from the book of Genesis. Both Josephs had fathers named Jacob, both had numerous prophetic dreams, and both saved their families by bringing them down to Egypt.
Luke, on the other hand, seems to have based his nativity story on 1 Samuel 1-3. When God tells Hannah (the mother of Samuel) through a priest that she would have a child, she responds "Let thine handmaid find grace in thy sight" (1 Samuel 1:18). When God tells Mary through an angel that she will have a child, she responds, "Behold the handmaid of the Lord; be it unto me according to thy word" (Luke 1:38). They sing a similar song. Hannah's song begins with "My heart rejoiceth in the Lord, mine horn is exalted in the Lord" (1 Samuel 2:1-10) while Mary's song begins with "My soul doth magnify the Lord, And my spirit hath rejoiced in God my Saviour" (Luke 1:46-55). Also, both Jesus and Samuel are taken to the Temple when they are of age (1 Samuel 1:22, Luke 2:41-50). Thus, in Luke, Jesus's grandfather isn't named Jacob as in Matthew, but rather Eli (Heli in Greek) after the grandfatherly priest Samuel served.
Jewish writings including the Talmud and the Tosefta state that Jesus was the illegitamate son of a Roman soldier named Panthera. Celsus, a second century Greek philosopher also made this claim. The 4th century Christian apologist Epiphanius tries to explain this away by claiming that the name "Jesus son of Panthera" is actually a nickname for Jesus's grandfather!
According to the Toledoth Yeshu, a Jewish document written between the 4th and 9th centuries based on an earlier oral tradition, Jesus lived during the reign of Queen Alexandra (about 100 BC) and was the illegitimate son of Yosef ben Pandera.
The evidence seems to indicate that Joseph, the father of Jesus, is a fictional character. Mark, Paul, and John tell us nothing about him while Matthew and Luke base their portrayal of him on characters from the Old Testament. Jewish and Pagan sources accuse Jesus of being illegitimate outright, while the Gospels merely imply that he is.
So what does all this mean for the question of the historical Jesus? The fact that Jesus was illegitimate was embarrassing for the early Christian church, so using the criterion of embarrassment, doesn't that mean he really existed?
Not necessarily. As we have seen, the Jesus of the Gospels is largely based on Old Testament characters and many Old Testament characters had questionable parentage. Jesus being illegitimate may have originally been a midrashic creation that later Christians found embarrassing and tried to change.