This is one of those issues where Catholic sources will tend to say the Fathers obviously called Peter the foundation of the Church (and supply quotes to prove it) and Protestant sources will tend to say they obviously did not (and likewise supply quotes to prove it). To get the full picture, you need to look at sources from both sides of the debate.
An ancient debate
It has been said that "few texts have been the occasion for the spilling of more ink than Matthew 16:17-19."1 Catholics, naturally, see the text as proof of the legitimacy of the papacy, while Protestants the verse as establishing the Church under the join authority of all the Apostles or via Jesus' own authority. One might think this is mostly a recent debate, but in fact debate about the meaning of this verse stretches back to the early days of the Church, long before any schisms arose.
The antiquity of this debate is made clear in a single passage by Augustine. In his final work, Retratations ("Re-treatments"; 428) Augustine wrote:2
In a passage in this book, I said about the Apostle Peter: "On him as on a rock the Church was built." This idea is also expressed in song by the voice of many in the verse of the most blessed Ambrose where he says about the crowing of the cock: "At its crowing he, this rock of the Church, washed away his guilt." But I know that very frequently at a later time, I so explained what the Lord said: "Thou art Peter, and upon this rock I will build my Church," that it be understood as built upon Him whom Peter confessed saying: "Thou art the Christ, the Son of the living God," and so Peter, called after this rock, represented the person of the Church which is built upon this rock, and has received "the keys of the kingdom of heaven." For, "Thou art Peter" and not "Thou art the rock" was said to him. But "the rock was Christ," in confessing whom as also the whole Church confesses, Simon was called Peter. But let the reader decide which of these two opinions is the more probable.
From this passage is it clear that at different points in his life, Augustine interpreted Matthew 16:18 as establishing Peter as the founder of the church, but at other times he believed the "rock" in view was actually Jesus, not Peter. As we look at other Church Fathers, we will see that both of these options are supported by multiple Fathers. In the end, Augustine didn't have a strong preference and left it up to the reader to decide for him or herself.
Tertullian (c. 160-240) wrote about the meaning of Peter and the Rock on several occasions. In Scorpiace ("Antidote for the Scorpion's Sting", c. 210), he wrote:3
For though you think heaven still shut, remember that the Lord left here to Peter and through him to the Church, the keys of it, which every one who has been here put to the question, and also made confession [of faith], will carry with him.
From this passage, Tertullian appears to be saying that the "keys" to the Church were passed on from Peter to the Church, which certainly could be read as an argument for apostolic succession and the papacy. Likewise, in De pudicitia ("On Modesty", c. 220), he wrote that "the Church" has the authority to forgive sins and as justification he writes:
what sort of man are you, subverting and wholly changing the manifest intention of the Lord, conferring (as that intention did) this (gift) personally upon Peter? On you, He says, will I build My Church; and, I will give to you the keys, not to the Church; and, Whatsoever you shall have loosed or bound, not what they shall have loosed or bound. For so withal the result teaches. In (Peter) himself the Church was reared; that is, through (Peter) himself; (Peter) himself essayed the key
He then goes on to describe a couple other ways in which Peter was primary: He was the first to "unbar" the entrance to heaven through baptism; and, he was the first to open the Gospel message to the Gentiles. As such, it is not hard to read this passage in support of papal succession. However, Tertullian concludes the passage by explaining what "the Church" is and says it is "properly and principally, the Spirit Himself" adding that any gathering of believers counts. He concludes:
And accordingly the Church, it is true, will forgive sins: but (it will be) the Church of the Spirit, by means of a spiritual man; not the Church which consists of a number of bishops.
which is certainly hard to read in a manner that would allow special authority for the papacy.
Tertullian clearly did believe in apostolic succession, for in De praescriptione haereticorum ("Prescription against Heretics", c. 200) he writes:5
For this is the manner in which the apostolic churches transmit their registers: as the church of Smyrna, which records that Polycarp was placed therein by John; as also the church of Rome, which makes Clement to have been ordained in like manner by Peter. In exactly the same way the other churches likewise exhibit (their several worthies)
However, there is no indication in this passage that the Church of Rome has a special authority. It certainly seems like he views all churches founded by apostles as equal.
It appears that Tertullian viewed Matthew 16:17-9 as conferring a special authority on to Peter. And he clearly believes in apostolic succession. However, if he believed that the Church of Rome, founded by Peter, received special authority, he did not make that clear.
The Epistle of Clement to James, supposedly a letter from Clement I (pope 92-99), supports the idea of papal succession through Peter. In truth in was not written by Clement, but rather an unknown writer around 220 AD. The fact that it is pseudographical is certainly problematic for doctrinal purposes and such, but does not mean the attitude of the writer did not reflect a common attitude of his day. "Clement" writes:6
Be it known to you, my lord, that Simon, who, for the sake of the true faith, and the most sure foundation of his doctrine, was set apart to be the foundation of the Church, and for this end was by Jesus Himself, with His truthful mouth, named Peter, the first-fruits of our Lord, the first of the apostles; ... But about that time, when he was about to die, the brethren being assembled together, he suddenly seized my hand, and rose up, and said in presence of the church: "Hear me, brethren and fellow-servants. Since, as I have been taught by the Lord and Teacher Jesus Christ, whose apostle I am, the day of my death is approaching, I lay hands upon this Clement as your bishop; and to him I entrust my chair of discourse
While the writer of this letter does not quote Matthew 16:18 directly, he perhaps alludes to it and certainly sees Peter as the foundation of the Church. Furthermore, he clearly believes in a special authority for the Church of Rome passed from Peter to Clement. The pseudographical nature of the letter does raise questions as to how mainstream the belief was at the time (people often wrote pseudographically when they wanted to elevate the legitimacy of a minority position), but there are other possible motives for the pseudography (e.g. to elevate the importance of Clement), so the belief may well have been mainstream. At minimum, the document establishes that the idea of papal succession founded on Peter began prior to 220 AD.
Similarly, it the Clementine Homilies, which may or may not have been written by the same hand, into Peter's mouth is put the claim to be the foundation of the church:7
For in direct opposition to me, who am a firm rock, the foundation of the Church, you now stand.
In his extensive commentary on Matthew (c. 250), Origen (c. 185-255) comments on the rock passage a couple times. In book 13, he writes:8
in the case of Peter, this saying "I will give to you the keys of the kingdom of the heavens," has been specially set before the words, "And what things soever you shall bind on earth," etc. And, indeed, if we were to attend carefully to the evangelical writings, we would also find here, and in relation to those things which seem to be common to Peter and those who have thrice admonished the brethren, a great difference and a pre-eminence in the things said to Peter, compared with the second class. For it is no small difference that Peter received the keys not of one heaven but of more
As such, it appears that he does see a special authority assigned to Peter. However, on the "rock" specifically he writes that every believer can "become a Peter" upon which the Church is built. He further argues:9
But if you suppose that upon that one Peter only the whole church is built by God, what would you say about John the son of thunder or each one of the Apostles? Are the keys of the kingdom of heaven given by the Lord to Peter only, and will no other of the blessed receive them? ... [anyone who professes belief] will obtain the things that were spoken according to the letter of the Gospel to that Peter, but, as the spirit of the Gospel teaches, to every one who becomes such as that Peter was. For all bear the surname of rock who are the imitators of Christ, that is, of the spiritual rock which followed those who are being saved, that they may drink from it the spiritual draught. But these bear the surname of the rock just as Christ does.
It seems pretty clear that Origen believes the church is not founded on the authority of Peter alone, but on all the Apostles. Furthermore, the promise passes not to a specific successor, but rather to all believers. All become the "rocks" on which the church stands.
Cyprian (c. 200-260) perhaps offers one of the most favorable statement for the Catholic position of papal primacy. In the first edition of De Ecclesiae Catholicae Unitate ("On the Unity of the Catholic Church", c. 250), he comments on Matthew 16:17-19, writing:10
On [Peter] he builds the Church, and to him he gives the command to feed the sheep, and although he assigns a like power to all the apostles, yet he founded a single chair, and he established by his own authority a source and an intrinsic reason for that unity. Indeed, the others were that also which Peter was, but a primacy is given to Peter, whereby it is made clear that there is but one Church and one chair. So too, all are shepherds, and the flock is shown to be one, fed by all the apostles in single-minded accord. If someone does not hold fast to this unity of Peter, can he imagine that he still holds the faith? If he deserts the chair of Peter upon whom the Church was built, can he still be confident that he is in the Church?"
As written this passage seems to be a clear endorsement of not only Peter as the founder of the church, but also a special authority for his successors. The picture is complicated a bit, however, because Cyprian released a second edition of De Ecclesiae Catholicae Unitate in which he revised this passage:10
Upon [Peter], being one, [Jesus] builds His Church, and although after His resurrection He bestows equal power upon all the Apostles... that He might display unity, He established by His authority the origin of the same unity as beginning from one. Surely the rest of the Apostles also were that which Peter was, endowed with an equal partnership of office and of power, but the beginning proceeds from unity, that the Church of Christ may be shown to be one.
Overall the gist of the passage is the same - all the Apostle had equal authority, but the Church was founded upon Peter specifically - but the language is considerably softened. Why did Cyprian make this change? A Protestant will, of course, say it was because the passage conveyed a higher degree of authority for Rome than Cyprian actually intended. However, this is not necessarily the case. In addition to changing the language, Cyprian significantly expanded the passage. It is possible that he was making the same argument in both cases - that Rome was given a special authority for the sake of Church unity - and was simply making it more clear that the Church at Rome wasn't "better", but rather only had a special (but equal) position.
Elsewhere (Epistle 39, c. 253), Cyprian wrote:11
There is one God, and Christ is one, and there is one Church, and one chair founded upon the rock by the word of the Lord. Another altar cannot be constituted nor a new priesthood be made, except the one altar and the one priesthood.
Given that we know Cyprian does equate the rock to Peter, it seems very likely that he means what he says in the first version of De Ecclesiae Catholicae Unitate. That is, that the Church at Rome does have a special authority via its foundation by Peter.
In a letter to Cyprian (c. 253), Firmilian (? - 270) uses Matthew 16:18-9 to say that Peter was given a unique authority to forgive sins, which through him was inherited by the Church:12
But what is the greatness of his error, and what the depth of his blindness, who says that remission of sins can be granted in the synagogues of heretics, and does not abide on the foundation of the one Church which was once based by Christ upon the rock, may be perceived from this, that Christ said to Peter alone, Whatsoever you shall bind on earth shall be bound in heaven, and whatsoever you shall loose on earth shall be loosed in heaven.
On the surface, this appears to establish papal authority and is sometimes quoted by Catholics as doing so. However, Firmilian continues:
And again, in the Gospel, when Christ breathed on the apostles alone, saying, Receive the Holy Ghost: whose soever sins you remit they are remitted unto them, and whose soever sins you retain they are retained. Therefore the power of remitting sins was given to the apostles, and to the churches which they, sent by Christ, established, and to the bishops who succeeded to them by vicarious ordination.
which casts doubt on whether he believed Peter's special authority was passed on to his successors specifically, as opposed to the Church as a whole. His position is made clear when, a bit later in the letter, he writes:
And in this respect I am justly indignant at this so open and manifest folly of Stephen, that he who so boasts of the place of his episcopate, and contends that he holds the succession from Peter, on whom the foundations of the Church were laid, should introduce many other rocks and establish new buildings of many churches; maintaining that there is baptism in them by his authority... Nor does he understand that the truth of the Christian Rock is overshadowed, and in some measure abolished, by him when he thus betrays and deserts unity.
It seems the letter was written in response to a letter by Pope Stephen I in which he argued that repentant heretics did not need to be (re-)baptized, but should be freely admitted to the Church. Apparently, Stephen claimed authority to decide such matters based on a special authority for his office, handing down through Peter. While Firmilian agrees that Peter was given a special position, he evidently strongly disagrees that this authority has been passed to Stephen in such a way that allows him to establish doctrine.
In a homily around the year 350, Cyril (c. 313-386) described the heretic Simon Magus making trouble in Rome and then remarked:
As the delusion was extending, Peter and Paul, a noble pair, chief rulers of the Church, arrived and set the error right
and then quotes Matthew 16:19 as justification for Peter's authority:13
For Peter was there, who carries the keys of heaven: and nothing wonderful, for Paul was there, who was caught up to the third heaven, and into Paradise, and heard unspeakable words, which it is not lawful far a man to utter.
From this passage, we can conclude that Cyril considered Peter (jointly with Paul) to be the first "ruler" of the Church and can place him at Rome. It is reasonable to think that Cyril was alluding to/supporting the idea of the papacy here, although as near as I can tell he did not comment directly on apostolic succession anywhere in his writings.
Writing in poetic form (c. 350; commonly described as a homily although not necessarily a homily in the modern term), Ephraim (c. 305-373) writes the following (presumably coming from Jesus' mouth):14
Simon, my follower, I have made you the foundation of the holy Church. I betimes called you Peter, because you will support all its buildings. You are the inspector of those who will build on Earth a Church for me. If they should wish to build what is false, you, the foundation, will condemn them. You are the head of the fountain from which my teaching flows; you are the chief of my disciples. Through you I will give drink to all peoples. Yours is that life-giving sweetness which I dispense. I have chosen you to be, as it were, the firstborn in my institution so that, as the heir, you may be executor of my treasures. I have given you the keys of my kingdom. Behold, I have given you authority over all my treasures!
Although it is not explicit, the most natural reading of this passage is that Peter is the first leader of the Church and is given a special authority. Furthermore, it is natural to see Ephraim as saying that authority is then passed on through a line of succession ("heirs").
In his untitled treatise against Donatism (c. 370), Optatus (?-387) repeatedly draws on Matthew 16:17-19 to establish the legitimacy of the papal teachings and the illegitimacy of Donatist anti-popes. For example:13
gates against which we read that Peter received the saving Keys - Peter, that is to say, the first of our line, to whom it was said by Christ: 'To thee will I give the Keys of the Kingdom of Heaven,' and these keys 'the gates of Hell shall not overcome.'
How is it, then, that you strive to usurp for yourselves the Keys of the Kingdom of Heaven, you who, with your arguments, and audacious sacrilege, war against the Chair of Peter?
In the same work, he writes:
You cannot then deny that you do know that upon Peter first in the City of Rome was bestowed the Episcopal Cathedra, on which sat Peter, the Head of all the Apostles (for which reason he was called Cephas), that, in this one Cathedra, unity should be preserved by all, lest the other Apostles might claim - each for himself - separate Cathedras, so that he who should set up a second Cathedra against the unique Cathedra would already be a schismatic and a sinner. Well then, on the one Cathedra, which is the first of the Endowments, Peter was the first to sit.
The word translated "Cephas" here is actually κεφαλή (kephale, literally "head"), hence Optatus is making a play on words similar to (but different from) Jesus' "rock/Peter". He doesn't reference the "rock" specifically anywhere in his work, but does reference the surrounding context - as illustrated above - and makes explicit reference to Peter conferring a special authority on the Church at Rome. (Optatus always explicitly endorses papal succession and includes a list of the popes, starting at Peter and continuing to his day.)
As we have already seen (in Augustine's commentary), Ambrose (c. 340-397) interpreted the rock passage as conferring a special authority on Peter. In Exposition of the Christian Faith (c. 380), he wrote:16
Could He not, then, strengthen the faith of the man to whom, acting on His own authority, He gave the kingdom, whom He called the Rock, thereby declaring him to be the foundation of the Church?
And in Enarrationes in xii. Psalmos Davidicos ("Commentary on Twelve Psalms of David"), he wrote:
This is that Peter to whom Christ said, ' Thou art Peter, and upon this rock I will build my Church.' Therefore, where Peter is, there is the Church;
In isolation, these passages seem to suggest that Ambrose not only viewed Peter as having a special position in the Church, but arguably also as supporting papal succession on this basis. However, his view was a bit more complicated than that as can to seen by, for example in Expositio evangelii secundum Lucam ("Exposition of the Gospel according to Luke") he writes:17
Christ is the rock, for ‘they drank of the same spiritual rock that followed them, and the rock was Christ’; also He denied not to His disciple the grace of this name; that he should be Peter, because he has from the rock the solidity of constancy, the firmness of faith. Make an effort, therefore, to be a rock! Do not seek the rock outside of yourself, but within yourself! Your rock is your deed, your rock is your mind. Upon this rock your house is built. Your rock is your faith, and faith is the foundation of the Church. If you are a rock, you will be in the Church, because the Church is on a rock. If you are in the Church the gates of hell will not prevail against you...He who has conquered the flesh is a foundation of the Church; and if he cannot equal Peter, he can imitate him.
In this passage, he seems to be saying Jesus is the "true Rock" on which the Church is founded and Peter's "rockship" is available to all believers, not just the pope.
There is sufficient evidence within the writers of the Church Fathers to find an early basis for the idea that "on this rock I will build my church" gives Peter a special position within Church history. There is also evidence that some Church Fathers saw this passage as a justification for a special place for the Bishop of Rome; that is, as a basis for papal authority. In some cases, the evidence is pretty clear, but in many cases it is ambiguous, and is some cases the writings appear to argue against the idea. Thus, no firm conclusion can be drawn about a collective teaching of the Church Fathers. Perhaps the most accurate statement would be that opinion was mixed as to whether Jesus started a special office via Peter.
It seems likely that the debate about what Jesus meant exactly by "on this rock I will build my church," which began in antiquity, will continue indefinitely. Neither those who believe Peter passed on a special authority to the Church at Rome nor those that deny it have a conclusive case in the writings of the Fathers.
1 "Peter the Rock" by Tim Staples at Catholic Answers
2 The Retractions (The Fathers of the Church, Volume 60) by Saint Augustine
3 Scorpiace by Tertullian at Tertullian.org
4 On Modesty by Tertullian at New Advent
5 Prescription against Heretics by Tertullian at New Advent
6 *Epistle of Clement to James at Tertullian.org
7 "Homily 17 at New Advent
8 Commentary on Matthew, Book XIII by Origen at New Advent
9 Commentary on Matthew, Book XII by Origen at New Advent
10 "The Unity of the catholic Church in The Faith of the Early Fathers by W. A. Jurgens
11 Epistle 39 by Cyprian at New Advent
12 Epistle 74 by Firmilian at New Advent
13 Catechetical Lecture 6 by Cyril at New Advent
14 "Homilies" in The Faith of the Early Fathers by W. A. Jurgens
15 Against the Donatists by Optatus at Tertullian.org
16 *Exposition of the Christian Faith, Book IV by Ambrose at New Advent
17 *A Commentary, by Writers of the First Five Centuries, on the Place of St. Peter in the New Testament by J. Waterworth