Once u got this u can Right-Click ur pet's portrait and press Abandon. Ur pet will be lost forever and won't be retrieveable. Then u can Tame another pet to your likings.
Another way is to visit a Stable Master, where you can store your pet. Then you can tame a new pet (a cat for example). You can change your pet at anytime you want at any stable master
To stable your pet for future use, find a Stable Master and store it there.
Once you get to level 10, you can learn the Tame Pet abiity, which makes you able to tame almost all beast type creatures
Since cata was released nearly all the tameable creatures will have some sort of special ability, some buff you, some debuff the mob they are hitting
Cats are great pets, they use a special roar that increases your (and any partys member) strength and agility for a short time
You are better off putting unwanted pets in the stables (visit a stable master, can be found in most towns and all major citys) and experiement with what pets suit you, or what ones you just really like the look of
Where are the pet stablers?
Just to add up on what Heathlour said.
Here is a list of all the Stable Masters:
Clicking on one of them will take you to a page where you can see the NPC's name (at the top) and an exact location on the map for where the NPC can be found.
Do note that Horde (H) NPCs are hostile to you when you play alliance, and will hence not be of any help to you.
Look for NPCs with 'green' coloured (A) (stands for 'Alliance'), as those NPCs will be friendly to you.
Lastly, note there are several pages of Stable Masters. You can go to the next page by clicking on 'Next' in the right hand corner.
The NPCs are currently sorted by 'location'.