The books never mention how the Trace is applied to young witches and wizards, and Accio Quote doesn't turn up anything relevant from interviews with Rowling. Any answer would have to be speculation. So I'll speculate.
I see two parts to this: how the Trace is applied, and when. Let's start with how.
Nobody who talks about the Trace in the books -- neither Moody, nor Ron or Hermione -- ever actually explains how or when it's applied, but we can gather some hints. From Ch9 of DH:
[Hermione:] "What if the Death Eaters have found a way to put [the Trace] on a seventeen-year-old?"
[Ron:] "But Harry hasn't been near a Death Eater in the last twenty-four hours. Who's supposed to have put a Trace back on him?"
So Ron is suggesting that a witch or wizard must be in the presence of the person they're applying the Trace to. It's not some country-wide enchantment that automatically applies the Trace to every wizarding child at birth / age eleven / first time they use magic / whatever; it's something that is done deliberately and in person.
It's possible that Ron doesn't actually know that the Trace must be applied in person, and is just guessing at the nature of the magic. But Ron's dad works at the Ministry, so it's entirely likely that he knows more about magical bureaucracy than Harry does; and Hermione doesn't correct (or even challenge) his assumptions. So that's fairly authoritative.
Now, as for when the Trace is cast on a person. It's obviously in effect by the time the student goes home after their first year at wizarding school, but it could start any time before that, perhaps even as early as birth. Can we narrow that down?
It's clear from numerous places in the books that the Trace isn't considered relevant until the student begins attending wizarding school. For example, in chapter 33 of DH:
[Snape:] "...and the Ministry can punish you if you do magic outside school, you get letters."
[Lily:] "But I have done magic outside school!"
"We're all right. We haven't got wands yet. [...] But once you're eleven [...] and they start training you, then you've got to go careful."
And in Ch13 of HBP:
[Dumbledore:] "But you should know that Hogwarts can expel students, and the Ministry of Magic -- yes, there is a Ministry -- will punish lawbreakers still more severely. All new wizards must accept that, in entering our world, they abide by our laws."
However, there's no indication of whether or not the Trace is actually in effect before the student enters school. Perhaps the Ministry simply ignores the Trace until the year the child would start attending wizarding school.
I can think of four main points of contact when the Trace could be applied.
At birth. If the child is born to at least one wizarding parent (e.g. Ron, Harry), it could be that registering your newborn with the Ministry, and having the Trace applied, is just part of the paperwork, like Muggle parents filing for a birth certificate (and with similar bureaucratic or legal consequences if the parents fail to do so).
However, it's less clear how this would work with Muggle-borns. Muggle parents don't meet a representative from the wizarding world until their child is soon to start their first year at wizarding school. Even if the child's name was down since they were born (as Hagrid said Harry's was), the new parents don't know that yet; they would have no way to know they needed to go to the nearest Ministry of Magic office to fill out paperwork, and have spells cast on their child.
It's possible that the Ministry has undercover workers in Muggle hospitals, just like they do in the Muggle government, post office, etc., and those undercover workers surreptitiously apply the Trace without informing the parents. But not all children are born in hospitals, and there are a lot of hospitals and not that many Wizarding folk to staff them all. So while it's possible, it seems awfully unlikely.
First contact. Harry was assumed to already know about magic, so his first contact from Hogwarts was simply the usual letter. Muggle parents, however, are visited in person by a member of the Hogwarts staff prior to their child's first year at Hogwarts (and this is the first time the parents are told that they aren't going crazy, and their child is actually a witch or wizard). It's possible that that staff member could apply the Trace as part of the visit.
Is there anything in the books to back this up? Harry's experience obviously isn't relevant; he just gets a letter (until his letters fail to get delivered, anyway). Hermione's visit is mentioned after the fact, and not shown in the narrative. But we do see Dumbledore's visit to Riddle. If he applied the Trace then, it's not mentioned.
Again, it's possible that the Trace is applied surreptitiously. But the only time Dumbledore takes out his wand during this encounter is to demonstrate magic (on the wardrobe, and then on its contents); he never turns his wand on Riddle directly. It's hard to imagine applying an enchantment that lasts six years without using a wand. (Okay, Harry's mother did better than that without a wand; and besides, it's Dumbledore. But still.)
When the student buys their wand. Given Snape's quote above, especially the bit about "we haven't got wands yet", this seems like a very practical time to apply the Trace. There are very few wandmakers, so it's entirely possible that they have to follow strict Ministry regulations.
There's no mention of Ollivander casting a spell on Harry. But it's possible that an enchantment is placed on the wands ahead of time, so that as soon as the wand chooses the wizard and establishes a bond, the Trace kicks in as well. (However, this conflicts with Ron's information that the Trace is cast in person.)
When the student starts their first year at Hogwarts. If students had to register for classes when they arrive, the Trace could be applied then -- but they don't; the classes are assigned. The only special things first-years do are:
- Cross the lake in the boats (but there's nobody who could cast the Trace on them then; the only adult with them is Hagrid, who isn't allowed to do magic);
- Gather in the side room prior to the Sorting ceremony (but there's nothing to suggest any special enchantment is applied while they're there); and
- Try on the Sorting Hat. Perhaps the Hat casts the Trace as they try it on. It's not clear that the Hat can cast spells of its own (beyond the obvious Legilimency), but it is a Thinking Cap, so who knows?
It's difficult to find an answer that fits all the facts. The Trace must be cast in person, but the narrative never reports anyone casting the Trace on Harry. It could happen at birth, but then special arrangements would have to be made (either at time of birth or sometime later) for Muggle-borns, and we never see those arrangements being made; they certainly don't happen on the day the students first arrive at Hogwarts, because the Muggle-borns never leave the group.
I personally like the idea of the Trace taking effect as the student buys their wand, as it would also cover students who are home-schooled or go to other schools (as long as there's not a black market in Trace-less wands), but it conflicts with what (little) we know about how the Trace is cast, so that's a mark against that theory.
The only answers that seem to fit everything we know are:
- McGonagall casts the Trace on the first-years while they're in the side chamber waiting to be Sorted -- but without getting out her wand, and without them noticing; or
- the Sorting Hat casts the Trace as it Sorts them.
Of course, there's always one final possibility: Rowling retconned the Trace into book seven for plot reasons, and it doesn't actually fit with anything that came before. Honestly, I think that's the most likely explanation of all.
But if we're sticking with canon, I'm probably going to go with the Sorting Hat.