One can find catechism-like fragments throughout Church history simply because catechesis is found throughout Church history. If you want a convenient point from which to identify the beginning of the catechism in the proper sense of the term, though, that is, a writing not consisting of lectures that systematically and topically arranges the foundational doctrines of the faith to serve as a guide to catechesis, it's useful to start with the fourteenth century, in which things recognizably what we would call a catechism appear. There tend to be two kinds, one in a simple question-and-answer format for the laity to learn, and another, more detailed, to assist the catechist, and both kinds continue until today.
What really makes the catechism take off, however, is the Protestant Reformation. Well before Luther, as early as the fourteenth century, it had regularly been recognized that catechesis was essential to reform of the Church. The Reformers carried this idea forward, and with them we find the beginnings of a process of refinement; taking the idea of a catechism, which had already developed, they began to improve upon it. This resulted in at least four major classic works, two of which were Luther's Small Catechism and his Large Catechism, both published in 1529. Luther placed extraordinary emphasis on the importance of catechesis, and devoted himself to it with a will; his exhortation at the beginning of the Large Catechism is well worth the reading. Starting with Calvin the Reformed tradition also produced catechisms regularly; the most notable in English were developed in the seventeenth century (1647-1648), namely, the Westminster Shorter Catechism and the Westminster Longer Catechism. The beginning of the Westminster Shorter Catechism has achieved almost legendary status:
Q. Quis hominis finis est præcipuus? (What is the chief end of man?)
A. Præcipuus hominis finis est, Deum glorificare, eodemque frui in æternum. (The chief end of man is to glorify God, and enjoy him forever.)
The publishing of catechisms was not a purely Protestant matter, however. And this brings us to the Jesuit, Peter Canisius, whose feastday is today. Canisius published three important Catholic catechisms: a long major form (1555), a very short minimus form (1556), and an intermediate minor form (1558). They quickly became the Catholic catechisms throughout the Catholic communities of Greater Germany, and then began to be translated into other languages all over Europe. "Knowing Canisius" became a common expression for being well-catechized, regardless of whether it was out of his books or not. Canisius's catechisms were a model for Bellarmine's catechisms at the end of the sixteenth century, and Bellarmine's catechisms in turn were raised up as a general model for Catholic catechisms.
Canisius was one of the most important theologians of his day. He attended the Council of Trent. He also attended the Diet of Worms and provided the primary Catholic responses to the arguments of Melanchthon -- and, indeed, it was his list of points that was actually under discussion when those attending discussed the Augsburg Confession. Canisius had the upper hand in the discussion, in part because (as he himself wrote in a letter to the Jesuit vicar in general) the Protestants were in complete disarray. One of Canisius's major points had been to note that there were divergences in the text of the Augsburg Confession, due to Melanchthon, who had both drawn up the original and also a later version that broadened the language of some of the clauses; and thus he and the other Catholic collocutors asked that the Protestants clarify what version they actually meant when they talked about it. The result was sheer confusion among the Protestants, who on the spur of the moment were unable to come to any agreement on the acceptability of Melanchthon's changes.
Nonetheless, Canisius was one of the more irenic voices of the Counter-Reformation, repeatedly insisting that polemical approaches should be avoided in dealing with Protestants; his letters to his superiors are full of complaints about the corruption of clergy, asking them to push for remedies, so he was well aware of the problems, and sympathetic to that extent. And he more than once insisted that the German people should be treated leniently because, decent and humble at heart, they could be brought about if treated with courtesy and if, instead of trying to force them into submission, someone just spoke honestly and plainly with them. A German himself (his name is Peter Kanis) he was very pro-German, a lover of German language and life. It is largely due to the work of Canisius, and his furthering of the Jesuits throughout the German provinces, that Bavarian and Austrian parts of greater Germany remained Catholic. His levelheadedness and generally irenic temper led him to be widely respected even by Protestants -- he was known as a man with whom, no matter how much you disagreed with him, you could always have a reasonable discussion. I say 'widely'; he was also criticized widely, in very sharp terms, because he was recognized as one of the major opponents of the Protestants, and his catechisms as a significant part of the Catholic response. But, opposed to polemic and ridicule to the very end, he refrained from attacking people and instead focused on arguments and claims. He stands as a testimony to the extraordinary power of intelligence combined with an ability not to take offense. Leo XIII described him as the Second Apostle to Germany, and Pius XI named him a Doctor of the Church. From one of his sermons:
It is not enough for the Gospel-teacher to please the people with his speaking. He must also be the voice of one crying in the wilderness, and so by his eloquence call many to the good life. He must not be a dumb dog, not even able to bark, as spoken of by the Prophet Isaiah. Yea, he should also burn in such a way that, equipped with good works and love, he may adorn his evangelical office, and follow the leadership of Paul....Those churchmen err who imagine that it is by brilliant preaching that they fulfil their office; rather, it is by holiness of life and all-embracing love.