St. Ignatius of Antioch (d. c. 107-110) used the term “catholic” (Gk. “katholikos”) in chapter 8 of his letter to the Christians of Smyrna in about 107 A. D.:
Wherever the bishop shall appear, there let the multitude [of the people] also be; even as, wherever Jesus Christ is, there is the Catholic Church.
I found a very helpful treatment of this topic in The Catholic Encyclopedia (c. 1910): available online (article, “Catholic”). It points out, however, that St. Ignatius’ use is not the technical meaning of the term as used today. For that specific usage it states:
[T]his sense undoubtedly occurs more than once in the Muratorian Fragment (c. 180), where, for example, it is said of certain heretical writings that they “cannot be received in the Catholic Church“. A little later, Clement of Alexandria [c. 150 – c. 215] speaks very clearly. “We say”, he declares, “that both in substance and in seeming, both in origin and in development, the primitive and Catholic Church is the only one, agreeing as it does in the unity of one faith” (Stromata, VII, xvii; P. G., IX, 552). From this and other passages which might be quoted, the technical use seems to have been clearly established by the beginning of the third century. In this sense of the word it implies sound doctrine as opposed to heresy, and unity of organization as opposed to schism (Lightfoot, Apostolic Fathers, Part II, vol. I, 414 sqq. and 621 sqq.; II, 310-312).
I looked up St. Clement of Alexandria’s Stromata, book VII. Here are the two occurrences of “Catholic Church” (chapter 17):
For that the human assemblies which they held were posterior to the Catholic Church requires not many words to show.
For the teaching of our Lord at His advent, beginning with Augustus and Tiberius, was completed in the middle of the times of Tiberius.
And that of the apostles, embracing the ministry of Paul, ends with Nero. It was later, in the times of Adrian the king, that those who invented the heresies arose; and they extended to the age of Antoninus the eider, as, for instance, Basilides, though he claims (as they boast) for his master, Glaucias, the interpreter of Peter.
Likewise they allege that Valentinus was a hearer of Theudas. And he was the pupil of Paul. For Marcion, who arose in the same age with them, lived as an old man with the younger [heretics]. And after him Simon heard for a little the preaching of Peter. Such being the case, it is evident, from the high antiquity and perfect truth of the Church, that these later heresies, and those yet subsequent to them in time, were new inventions falsified [from the truth].
From what has been said, then, it is my opinion that the true Church, that which is really ancient, is one, and that in it those who according to God’s purpose are just, are enrolled. For from the very reason that God is one, and the Lord one, that which is in the highest degree honourable is lauded in consequence of its singleness, being an imitation of the one first principle. In the nature of the One, then, is associated in a joint heritage the one Church, which they strive to cut asunder into many sects.
Therefore in substance and idea, in origin, in pre-eminence, we say that the ancient and Catholic Church is alone, collecting as it does into the unity of the one faith — which results from the peculiar Testaments, or rather the one Testament in different times by the will of the one God, through one Lord — those already ordained, whom God predestinated, knowing before the foundation of the world that they would be righteous.
But the pre-eminence of the Church, as the principle of union, is, in its oneness, in this surpassing all things else, and having nothing like or equal to itself. But of this afterwards.
Since St. Clement died around 215, this use of the title was clearly established by that time, and quickly became widespread, and standard usage by the fourth century.