Looking around the world, Christianity has spread to practically every corner. Christians are everywhere from South America to Australia to Korea. Even with Christian missionaries going all over the place, did people just pick it up and believe?
Since we're in the History SE I'll answer this from the historical perspective (and not the modern one where religious freedom is sacred to many countries).
In the middle ages in Europe, the freedom to choose one's religion wasn't often available. In fact quite often a monarch would attempt to force all his subjects to accept his religion. This is a major cause of religious wars. The Thirty Years' War is an example (this was also the last great religious war).
The war was preceded by the election of the new Hapsburg Holy Roman Emperor, Ferdinand II, who tried to impose religious uniformity on his domains, forcing Roman Catholicism on its peoples. The northern Protestant states, angered by the violation of their rights to religious liberty, which had been granted in the Peace of Augsburg, banded together to form the Protestant Union. Ferdinand II was a devout Roman Catholic and much less tolerant than his predecessor, Rudolf II, who ruled from the largely Protestant city of Prague. Ferdinand's policies were considered strongly pro-Catholic and anti-Protestant.
Note this paragraph refers to the "northern Protestant states". In modern times it's inconceivable that an entire state can be Protestant, but it happened in history. The rulers of the northern states imposed religious uniformity, but rebelled when religious uniformity was imposed on them.
Given this, then, the real question is why rulers adopted Christianity in the first place (if they adopt Christianity then their entire country adopts it, spreading the religion). As you may be aware, early Christianity did not do well, and it was a persecuted religion, especially after the burning of Rome in 64 AD. However, in 312, something dramatic happened that led to the then Roman emperor, Constantine the Great, converting.
Eusebius of Caesarea and other Christian sources record that Constantine experienced a dramatic event in 312 at the Battle of the Milvian Bridge, after which Constantine claimed the emperorship in the West. According to these sources, Constantine looked up to the sun before the battle and saw a cross of light above it, and with it the Greek words "Ἐν Τούτῳ Νίκα" (in this sign, conquer), often rendered in a Latin version, "in hoc signo vinces" (in this sign, you will conquer). Constantine commanded his troops to adorn their shields with a Christian symbol (the Chi-Rho), and thereafter they were victorious.
There's one more factor: Christianity is an evangelical religion, i.e. its adherents attempt to convert others to their religion. This led to holy wars. You may have heard of the Crusades which were aimed at reconquering the Holy Land after it was conquered by Muslims, but there were also Crusades aimed at forcing non-Christians to convert. This process lasted for much of the middle ages and ended when Lithuania, the last Pagan nation in Europe, converted to Christianity in 1387 (see also the plenty other Christianization of X articles on Wikipedia). So no, people did not just "pick up and believe" the religion; plenty had to be forced to convert.