I actually wrote a paper on this in undergrad. The origins go back to the Roman empire and predate most of the land issues. It comes from a few passages in Paul's letters where he states that it is better to abstain from sex if possible, but if someone isn't capable of abstaining, then marriage was the second-best option. Also, at the same time asceticism was seen as a positive sign among pagans and christians alike, as it was a symbol that one had moderated their passions with religion/philosophy and ascetics had a great deal of moral influence in the early church. In this regard, abstaining from sex was part of abstaining from food, shelter, sleep, and all the other "wordly" things. Early christian leaders would often be chosen from among those who abstained from sex because it was seen as a sign of moral virtue and leadership.
As to when it became mandatory, I didn't get into that, but I believe that politics did play a role. By way of contrast, the Eastern Orthodox Church, which is the other half of the ancient church and just as old as the Catholic Church, requires celibacy only for church members who are at the bishop level or higher, but not for local priests. The thinking being that the high-level leaders of the church should be drawn from the really virtuous people who are capable of abstinence.