When you mouse over a beast to skin it, if the word "Skinnable" is grey, you will not receive a skillup for skinning it. Same with recipes, ones in grey text will not increase your skill.
For most professions, you have a chance to gain skill level as you craft items, perform your service, or gather from a resource. As you increase in a skill, more recipes and resources reach a 0% chance to increase the skill (at this point the recipe will appear grey in the profession window). When a recipe turns green, a skill raise seldom occurs. A yellow recipe will raise the skill by 1 point roughly 60% of the time. An orange recipe always raises the skill 1 point.
And some detailed info about skinning skill increases, also from Wowpedia
Any skinnable corpse will have a color code on the "Skinnable" property when you move your pointer over it:
Red: Not skinnable.
Orange: Difficult to skin; high chance of increasing Skinning skill level.
Yellow: Moderately difficult to skin; moderate chance of increasing Skinning skill level.
Green: Easy to skin; low chance of increasing Skinning skill level.
Gray: Very easy to skin; no chance of increasing Skinning skill level.
Skinning skill required is:
1 for level 1-10 mobs.
(10 times mob level) minus 100 for level 11-20 mobs.
5 times level for level 21-79 mobs.
5 times level plus 25 for level 80 and higher mobs, including mobs from Wrath of the Lich King.
Up to skinning 100, you can find out the highest level mob you can skin by: ((Skinning skill)/10)+10.