A critical hit (crit) is a hit that strikes a vital area and therefore deals double damage or more. To score a critical hit, an attacker must first score a threat (usually a natural 20 on an attack roll) and then succeed on a critical roll (just like another attack roll).
Critical hit damage is usually double damage, which means rolling damage twice, just as if the attacker had actually hit the defender two times. (Any extra damage dice, such as from a rogue's sneak attack, are not rolled multiple times, but are added to the total at the end of the calculation). This is explained in greater detail below.
Critical Hit Immunity
Some creatures are simply immune to critical hits, and not even a natural 20 will overcome this. In addition, any creature that is immune to critical hits is also immune to other, similar effects which rely on hitting an enemy in a vital area. These include Sneak attack and Precise strike, among others. This is usually mentioned in the feat or effect description.
Likewise, some feats can partially bypass critical immunity. Epic Precision allows the user to deal 1/2 her normal sneak attack damage to critical-immune creatures, but does not allow her to get critical hits against them (this also helps other sneak-attack feats like Death Attack, but probably has no effect on others like Precise Strike). One Shot actually ignores critical hit immunity entirely (and always gets a critical hit).
Critical Hits Explained
There are three stages to a critical hit: Threaten, Confirm, and Multiply. 
When you roll a threat on your attack roll, this means the d20 roll (natural roll) must fall within the weapon's threat range. The critical hit information on each weapon is divided into two parts: the threat and the multiplier. The critical threat is the first number or range of numbers in this description. For example, a Longsword says 19-20/x2, meaning it has a threat range of 19-20 and a multiplier of x2 (more on multipliers below).
Thus if you roll a 19 or a 20 with a longsword you have "threatened" a critical hit. Likewise, on a Scimitar the range is 18-20, meaning a natural roll of 18, 19, or 20 will threaten a critical. Other weapons, like a Spear, only threaten on a natural 20 (but typically offer a better multiplier).
If you do not hit your opponent the critical threat is (obviously) ignored. Likewise, you cannot get critical hits against enemies that are immune to criticals, no matter what you get on a natural roll.
There are several ways to increase your critical threat range, such as carrying a keen weapon, learning the Improved Critical feat, or taking 7 Weapon Master levels to gain the Ki Critical feat. Note that multiple instances of keen do not stack with each other, and keen does not stack with Improved Critical. Ki Critical does stack, adding the +2 to the range after Keen or Improved Critical has doubled the range.
Threatening a critical is not enough. Now you must confirm that you actually struck the target in a vital or exposed place by succeeding at another attack roll. This is not attacking again, it's simply a duplicate attack roll to confirm the critical hit. You get all the normal modifiers of the first attack roll, except the confirmation roll does not automatically hit if a natural 20 is rolled, nor does it automatically miss if a natural 1 is rolled. You simply have to roll high enough to hit your opponent (beat his AC rating) when confirming the critical.
The threat roll can be increased by the Power Critical feat, which adds +4 to the confirmation roll.
Once you've confirmed the critical, the final step is to multiply the damage dealt. The amount to multiply by is the weapon's critical multiplier, found next to the critical range in the weapon description. For example, a Longsword has a multiplier of x2, meaning it deals double damage on a critical hit. A Scythe has the highest multiplier, at x4.
The multiplier amplifies the weapon's base damage and most damage modifiers by that amount. Because not everything is multiplied during a critical hit, a longsword (for example) won't always do exactly double damage. Most variable damage (die rolls like 1d6, etc) is not multiplied, nor is elemental damage on a weapon (even the constant +2 from adamantine). However, the majority of other damage modifiers do multiply out.
A character with Greater Weapon Specialization (+4 damage) and Improved Power Attack (which is active at the time, giving +6 damage), a +5 Strength modifier, and an Adamantine Longsword +5 with +1d6 acid damage and +2 magical damage makes a critical hit. He is holding a shield so the longsword is being held one-handed, and the longsword's multiplier is x2. The damage dealt is:
2*1d8 (longsword base damage) + 2*5 (strength modifier) + 2*6 (Improved Power Attack) + 2*4 (Weapon Specialization) + 2*5 (+5 weapon enhancement bonus) + 2 (adamantine's +2 magical damage) + 1d6 (acid damage).
The multiplier is applied before any dice are actually rolled, so this simplifies to:
= 2d8 + 10 + 12 + 8 + 10 + 2 + 1d6
= 2d8 + 42 + 1d6
Assuming there are no other damage modifiers in play (or damage resistance etc), this means our example character will deal 45 - 64 damage per critical hit. Normally he would deal 24 - 36 damage.
Computing Average Bonus Damage
The maths behind critical hits is fairly simple, and useful in evaluating the effects of various abilities such as improved critical or weaponmaster bonuses. For each attack that hits, there is a chance x (the range of the critical) out of the number of numbers you hit on (here denoted as y) that the hit will be a critical threat. Of those x/y numbers, the chance you get a critical hit is the number of numbers you hit on (y) out of 20. So the average number of critical hits is (x/y)*(y/20), which simplifies to x/20. This means that for each critical range step (20, 19-20, 18-20, etc) there is a 5% chance that a given hit will be a critical hit. The only exception to this is that if the number of numbers you hit upon is less than the number of numbers you critical threat upon, the formula reduces to y/20 because attacks which don't hit can't critical threat, and only natural 20s are guaranteed to hit.
This means that a 19-20 x2 weapon gains exactly as much bonus damage from critical hits as does a 20 x3 weapon, being a 5% chance of 2x(things that are multiplied) bonus damage or a 10% chance of 1x(things that are multiplied) bonus damage. Also, this means that a keen 19-20 x2 weapon (with a threat range 17-20) gains exactly as much average bonus damage from criticals as a keen 20 x3 weapon (with a threat range of 19-20). The same applies for the Improved Critical feat (which is equivalent to having the keen property on your weapon).
For a 5th-level (or 6th-level) Weapon Master, who gets the Increased Multiplier feat, (which increases a x2 critical to x3, a x3 critical to x4, etc), a 19-20 x2 weapon is preferable to a 20 x3 weapon, since these effectively become 19-20 x3 and 20 x4 weapons respectively. However, the Ki Critical feat (aquired on level 7) favours weapons with higher multipliers since it adds to the threat range (and does not multiply it, as the Keen property does). Thus, the weapons effectively become 17-20 x3 and 18-20 x4 weapons respectively, which are equivalent. [Actually, not: 17-20 x3 and 18-20 x4 is like 28 against 29, what means 18-20 x4 is better.]