I understand that it means to acquire a new skill, but what does it refer to? It makes me cringe every time I read it!
OP is mistaken about the exact meaning of the expression. It's not about acquiring "new" skills, but about how you got started on the skills you already have. Here's a definition from dictionary.com
It's a metaphoric reference to when a baby's teeth first appear. They grow (cut) through through the gums - often painfully, which also gives us the figurative usage teething troubles.
Once the baby has "cut its teeth", it's properly equipped for the all-important "real-world" task of chewing solid food (metaphorically, for tackling more complex problems in professional life, etc.).
As that dictionary example suggests, the expression is often used boastfully/facetiously (in reality the hunter probably started with much less challenging prey, such as grubs, mice, and rabbits).