Where did our spirit come from? Did it exist before we were born? Or did it come into existence when we were born or later?
What is an overview of the major Christian answers to this question?
The discussion of the origin of the human soul/spirit (on this topic they are generally spoken of as one immaterial part) is a very old one in Christian history. There are many serious implications which the debate has commonly hinged on, particularly regarding the transmission of Adam's original sin and guilt. However varied those theories may be, a basic summary shows that most variations of views on this topic fall within a few categories:
Creationism (of the soul) believes that God creates a soul for each body that is generated organically. 
Historically, Creationism has been the default explanation of the early church and is now still maintained by the Roman Catholic Church.
Jerome was clear in his support of it while opposing Traducianism (below). He is joined by Augustine, though he expressed doubts to Jerome later in his life as he debated with Pelagius on the topics of original sin, guilt and the human condition. 2
By the 13th century, creationism was solidified in the Roman Catholic Church by notables such as Thomas Aquinas.
Creationism has many verses that would seem to support it:
Ecclesiastes 12:7 (ESV)
and the dust returns to the earth as it was, and the spirit returns to God who gave it.
Isaiah 42:5 (ESV)
Thus says God, the Lord,
who created the heavens and stretched them out,
who spread out the earth and what comes from it,
who gives breath to the people on it.
Zechariah 12:1 (ESV)
The oracle of the word of the Lord concerning Israel: Thus declares the Lord, who stretched out the heavens and founded the earth and formed the spirit of man within him.
Traducianism posits that the immaterial and the material are generated through the organic process of generation, or conception. Though very similar, Generationism is sometimes distinguished from Traducianism in that it would say that the parents' souls are involved in the generation of the child's immaterial part while their bodies generate the organic, rather than the organic process being responsible for both. 
In both cases, neither of the two explanations traditionally maintains that God is not involved at all, which is a common criticism and misconception. Both explanations, however, insist the parents provide the substance while God provides the spark. 
Tertullian is one of the earliest theologians (ad 160?-230?) to argue strongly for Traducianism. Soon after the rise of the Pelagian heresy, many church fathers, such as Augustine, began to question this topic and Traducianism became a popular alternative. Gregory of Nyssa is another major early proponent of Traducianism.
Eastern Orthodoxy held to Traducianism, and it was popular with Lutherans after the Protestant Reformation.
Psalm 51:3 (ESV)
Behold, I was brought forth in iniquity,
and in sin did my mother conceive me.
9 One might even say that Levi himself, who receives tithes, paid tithes through Abraham,
10 for he was still in the loins of his ancestor when Melchizedek met him.
Others believe that God created souls either before he created Adam and Eve or along with the souls of Adam and Eve on the 6th day, and the souls are then breathed into their new bodies, as Creationism says, at conception.
There are some, however, who would not necessarily agree the soul was created at all but is already eternal, is waiting to be placed in a body, and the body and soul will one day be reunited in eternity.
Another solution is to avoid the question entirely. Christian Mortalism (Monism or Materialism), regardless of differing eschatological beliefs, would say the soul (or spirit) and the body are not separate but are united. Accordingly, Christian Mortalism is similar to Traducianism in that a person's soul is created in the union of the parents without an immaterial part to create, but only one whole person.
However, that is not to say that all materialistic or monistic theologies hold to this belief. The 7th Day Adventists, for example, are primarily Creationists (either declared or undeclared) with strongly monist tendencies.