As far as we know, he did not use this analogy. It does not appear in the extant writings attributed to him, nor in early hagiographies. There are several places in these documents where a shamrock metaphor wouldn't go completely amiss, and yet it doesn't seem to appear anywhere.
In the Confession attributed to Patrick, he talks a lot about how he is a simple unlearned person, who has nevertheless managed to convert a large number of people. That might suggest use of easily-understandable metaphors rather than very precise theological statements. On the other hand, there are biographies that say he studied under Saints Germanus of Auxerre and Martin of Tours, received large numbers of books from Pope Celestine I, and so forth, suggesting that he might have understated his level of education. His reported speech is generally quite direct and Biblical - more of a "repent, ye sinners" flavour than any kind of gentle analogy.
Given the complete lack of reference until the eighteenth century, it seems more likely that the explanation was associated with him long after he actually lived, than that it was somehow preserved in tradition for the whole time, without appearing in any of the many written sources about this popular saint.
I'll now give some examples of shamrocks not appearing. There is a fifth-century poem or hymn attributed to him, called the Lorica of St. Patrick (Luireach Phadraig) or Deer's Cry (Faeth Fiada), which invokes the Trinity but does not use an analogy. The ninth century hagiography known as the Tripartite Life (Bethu Phátraic) recounts an episode where Patrick converts the two daughters of Lóegaire mac Néill, saying in response to their question about what kind of God he worships:
St. Patrick, full of the Holy Spirit, responded, "Our God is the God of all, the God of heaven and earth, the God of the seas and rivers, the God of the sun and moon, and all the other planets; the God of the high hills and low valleys; God over heaven, in heaven, and under heaven; and He has a mansion, that is, heaven, and the earth, and the sea, and all things that are in them. He inspireth all things. He quickeneth all things. He enkindleth all things. He giveth light to the sun, and to the moon. He created fountains in the dry land, and placed dry islands in the sea, and stars to minister to the greater lights. He hath a Son, coeternal and coequal with Himself; and the Son is not younger than the Father, nor is the Father older than the Son. And the Holy Ghost breatheth in them. And the Father, and the Son, and the Holy Ghost are not divided. I desire, moreover, to unite you to the Son of the heavenly king, for ye are daughters of an earthly king." 1
This would be the perfect time to mention the shamrock, but it does not appear. The same goes for the seventh-century Life by Muirchú moccu Machtheni, and the other sources. It is frequently mentioned that people in Ireland did not generally know about or believe in the Trinity before Patrick, and that he baptized people in the name of the Trinity, but there is no record of him using any metaphor for it, shamrock or otherwise, when he baptized or taught.
Tertullian's work Against Praxeas (Adversus Praxeam) uses a plant metaphor for the Trinity (chapter 8). Here, he says that the three persons of the Trinity are like the root, trunk, and fruit of the tree. This has something of a similar character to the shamrock metaphor, though the three parts for Tertullian have distinct roles2, and the clover leaves are all the same. It is possible that Patrick had some exposure to this idea, or independently reinvented it. But there is absolutely no evidence.
1. From the translation by James O'Leary, 1874. Original Latin and Irish text is on lines 1124-1138 of Kathleen Mulchrone's 1939 edition.
2. Partialism!? Modalism?! Perhaps. Metaphors are hard.