I see some characters with pets. How do I get one?
There are two different types of pets: class pets and companion pets. The former you only get if you're a certain class: warlocks get demonic minions, hunters can train animals to be pets, death knights can get undead pets, and frost mages can get a water elemental as a pet.
But I have a feeling you're talking about so-called companion pets. Companion pets are rewards for all sorts of things: achievements, quests, out-of-game events; some are even available for purchase with real money.
The best way to find out how to get one is to figure out the companion you'd like to have first, and find out what you need to do to get it. To that end, the website WarcraftPets.com has a searchable database that gives all the details about the different companion pets.
The other answer is quite outdated. Since the Mists of Pandaria expansion was released, which added "Battle Pet" functionality, and the Pet Journal screen.
There are now three types of pet in World of Warcraft:
There is no level restriction on getting Companion or Battle Pets, however class pets usually unlock as you level up. Additionally, while Companion and Battle Pets appear in the pet journal, class pets appear in the skill book instead.
Any pets that you collect will be browsable and selectable from within the Pet Journal.
The Pet Journal is accessible by clicking on the Mounts icon on the toolbar and then selecting the "Pet Journal" tab:
All battle pets can act as companion pets, but not all companion pets can act as battle pets. The distinction is usually reserved for extremely rare companion pets. A full list of pets and where you can get them from is available at the WoW Pet Database.
The easiest way to get hold of some of the more common pets is through the in game auction house, under "Pets". You can normally pick up some of the easier to find pets for less than 1 gold, although for the rarer pets this can increase quite rapidly to several thousand gold.