How did Psalm 124 become associated with the Holy Innocents? The Holy Innocents are the children mentioned in Matthew's gospel (2:16-18) as having been murdered by Herod. Many churches celebrate a Feast of the Holy Innocents, or Childermass, on one of the days following Christmas Day.
Psalm 124 (or 123 in the Vulgate) is often chosen as an appointed reading, for example in the Evangelical Lutheran Church of America, the Church of England, and the Roman Catholic Church. Here's verse 7 in the KJV and the Vulgate:

Our soul is escaped as a bird out of the snare of the fowlers: the snare is broken, and we are escaped.
Anima nostra sicut passer erepta est de laqueo venantium: Laqueus contritus est, et nos liberati sumus.

Musical settings include those by Michael Haydn (offertory Anima nostra, MH146, performed here by the Vienna Boys Choir) and Palestrina (Anima nostra sicut passer).
I was wondering when and why this psalm text became associated with Matthew's story.
It is well-represented now in the lectionaries of several different churches, as shown above, but it does not seem to be referenced in the earliest such texts. For example, the fifth-century Leonine Sacramentary refers to Jeremiah 31:15 (which is clearly directly relevant, since Matthew quotes it!) but not to this psalm. In other words, who decided, and on what basis, that the psalm was a good match for the Holy Innocents?
To me, the imagery from the psalm perfectly represents Christ's escape from the killings that were taking place shortly after his birth. The psalm pictures our soul's escape from sin through the destruction of the snare much the same way Joseph's vision foiled the trap that was laid for the Christ. That seems to give the why pretty well.

As for the when, I am still looking for an answer to that question.