The chance that the villager gains experience when they succeed at a skill is random, but you have to gain a certain amount to become a trainee/adept/master -- for example, as far as I can tell, a villager has to gain skill 3 times to go from unskilled to trainee. That might happen the first three times they are successful, it might take 5 or 6 times.

The difference is the chance that they will gain skill -- the more skill they have, the less likely that they will gain skill. It takes more effort (like getting a PhD. vs. finishing high school -- trust me on this one, the PhD. is a LOT more difficult ).