Skinning is one of the most profitable professions you can pick up. It's fairly easy to level but gets time consuming toward the end, but there are no expensive things to purchase or make, just time spent. If you're skinning to level your leatherworking you may want to just buy the supplies in the Auction house.
Since patch 2.4 was implemented you can now train up to Artisan Skinning at any trainer available. To get your skill past 300 you will need to see the Master Skinning Trainer that is located in each factions appropriate starting city for the Burning Crusade in Hellfire Peninsula, Honor Hold and Thrallmar.
For easy use purposes the first two sections are combined into one to avoid duplicating zone maps. The Alliance and Horde Territories are clearly mapped out so there aren't any unexpected deaths. There's nothing special with skinning, just remember that you can skin a mob that is generally speaking your current skill divided by 5. If you have a skill of 100 you could expect to be able to skin a level 20 mob (100/5). In these beginning areas you can run around just skinning random beasts in the starting zones.
Part of journeyman skinning is in these maps from 130-150, but they've been rolled into expert skinning to be more efficient. You can do skinning from 150-180 in Arathi if it is easier for you. 180-250 and beyond can be done in Stranglethorn Vale, it depends how long you want to stay there.
The Hinterlands is one of the best skinning mobs as you go from the west to the east, the mobs increase in level and skinning difficulty. There are wolves of all sorts of levels and you can finish to 300 on the turtles along the shore. Azhsara is another good alternative zone to The Hinterlands.
You'll skill up less frequently from 300-375 so you may find yourself skinning an yellow/orange mob and not getting a skill up. Don't worry, the hardest part is from 300-310 it seems to get better or you get used to it. You can go all the way to 375 in Hellfire Peninsula if you wanted, but its faster to hit only 330 and move on to Nagrand.
In Nagrand you can also get to 375 if you want to and it is probably almost as efficient as going to Blade's Edge Mountains to skin, but go wherever you like.