The early Christian communities were self-governing. The local Christians elected their leader, the bishop. (Modern Amish communities still do the same thing.) The word comes from the Greek, as do all words from early Christianity, episkopos, meaning someone in charge, an overseer (think of the root epi-, as in epicenter, plus "scoping things out"). The word became episcopus in Latin; take the -e- off the front and you'll see where we get the word 'bishop'.
Early Christian bishops tried to coordinate, but no one was in charge of the others. Any sort of dispute or question would be settled by a council, where the bishops would meet, discuss, and vote. One of the most important early councils was Nicaea of 325, which determined the nature of the Trinity. At this point, the Emperor Constantine was beginning to tolerate Christianity (he was baptized on his deathbed), so bishops were able to make their religion and their flocks more public and start building churches. A cathedral (on which see more here) is a church for a bishop.
Each bishop was in charge of a diocese, his region, which in the old Roman Empire corresponded to the pagus, the basic geographic unit of imperial administration. In the west, counties, headed by counts, also corresponded to the pagus, creating tensions between bishop and count throughout the Middle Ages.
Early bishops were married, with families, though by the sixth century western bishops generally were single or widowed—or adopted separate bedrooms. In Byzantium, however, where early Christianity evolved into Greek Orthodoxy, bishops still married. Modern Protestantism, self-consciously following the practice of the early church, returned to married bishops.
By the fifth or sixth century, it came to be taken for granted that five bishoprics were "first among equals," those of Rome, Constantinople, Alexandria (a great learning center in Egypt), Jerusalem, and Antioch (Peter's city, according to the New Testament). They were honored with the title 'papa', meaning (naturally) Daddy. With the rise of Islam in the seventh century, all of these cities except for Rome and Constantinople had Christianity essentially disappear, leaving only the bishops of Rome and Constantinople, the forerunners of the pope and the Greek Orthodox patriarch (see more here on early medieval popes).
In practice, bishops, not popes, continued to run Christianity between them until the eleventh and twelfth centuries, as discussed more here. Bishops held councils to decide any important issues and were still locally elected, by both powerful lay people and by the priests of the diocese. During the twelfth century, however, election was restricted to the cathedral canons, the priests who served the cathedral and helped the bishop run the diocese. In the thirteenth century, popes began insisting that they, and only they, could choose bishops.