Not every class gets to parry. Warriors learn it at level 6, hunters and paladins at level 8, rogues at level 12 and death knights start with parry. Shamans learn it via a 20-point talent in the Enhancement tree. For the rest, you have to have more parry chance than is reduced by the opponent's expertise and extra weapon skill (e.g. you won't parry an opponent of much higher level), and you must be facing the enemy and wield a weapon.