Critical hits

I don't think that any of the "old school" editions of D&D ever formally enshrined the wildly popular "critical hit" rule.  It's certainly not in B/X or BECMI. My experience with AD&D (both 1st and 2nd edition) is fairly limited, but I don't recall seeing critical hits in those rulebooks, either.  I can't even imagine such a thing being included in OD&D.

Actually, I should say that none of these editions had a universal critical hit rule.  Old school D&D does, however feature quite a few special cases that specify a special effect which occurs on a high enough attack roll.  Such ad hoc applications don't constitute true critical hit rules, but they do conform to the general concept.

Peruse the monster chapter in the Expert Rules (Cook or Mentzer) and you'll notice at the beginning a list of special attacks.  Two stand out: Swallow and Swoop.  A swallow attack occurs on a natural 20, and for larger creatures may occur on lower numbers as well.  The most iconic example of a Swallow attack is that of the purple worm, which succeeds on an attack roll which exceeds the minimum roll needed by 4 or more.  Swoop attacks are used by flying creatures; on a roll of 18 or better, the creature grasps the target and flies away with it if it can lift the target's weight.  Some other special moves, such as a bear's "hug" attack which is activated by two successful paw strikes, have some shades of critical hit to them as well.

Player characters aren't entirely left out.  The Companion Set (the C in BECMI) has the sword of slicing, a magical weapon which reduces the target instantly to 0 hp on an attack roll of 19 or 20 if a save vs. death ray is failed, and inflicts triple damage even if the save is made.  AD&D has the vorpal sword and sword of sharpness, which inflict their severing effects on a high enough attack roll.  There are also the optional Weapon Mastery rules of the Mentzer edition Master Set and the Rules Cyclopedia, which grant a few weapons the ability to inflict double damage or other special effects on a high attack roll at high levels of mastery.

So, the basis for critical hits, at least in narrow applications, really is all right there in the manual.  How much these narrowly focused cases inspired or influenced the broader application of critical hit rules I have no idea.  It does seem rather strange that, with all the wildly unbalancing stuff the official rules poured into the game, a relatively mild tweak like the critical hit has remained exclusively the province of house-ruling, never even meriting an Optional Rules mention from the folks at TSR.

There's no single right way to implement a critical hit rule.  Different variations have different mechanical effects in play.

• Critical hit on a natural 20 has the virtue of making them fairly infrequent, but also has the effect of making criticals against heavily armored targets as likely as against unarmored ones.  Also, if you have a target that a character can only hit with a 20, every time he does manage to penetrate its defenses he does critical damage, which seems a bit wonky.
• Critical hit when the roll exceeds the number needed by a certain amount tends to give fighters (and monsters!) an advantage over other classes, and makes heavily armored targets less susceptible than lightly armored ones, but also drastically ramps up the damage potential, and thus the lethality, of combat.  If a critical happens on an attack that succeeds by 5 or more, then a 1st level fighter with no bonuses fighting an AC 6 monster - pretty typical for a low-level opponent - is going to crit on an 18-20.  With a +2 bonus from Strength, that widens to 16-20, or 25% of all attacks, and fully half of those that hit will be criticals.  You can set the "buffer" number higher than 5, of course, but as the characters advance in level, criticals will become more common.  Not that that's automatically a bad thing, because they're probably going up against opponents with a lot more hp, as well as having more themselves.
• The most common result of a critical hit is double damage.  Rolling twice the number of dice gives a solid average, and minimizes the chances that your glorious crit does chump damage, but also decreases the odds of max damage.  Rolling the usual dice and doubling the result gives a higher chance of max damage, but also a higher chance of minimum - the spread is exactly the same as for a non-critical. 
• Or, just do the attack's max damage without rolling, which makes every critical hit a solid blow without inflating total damage potential.
• Or, roll on a Death and Dismemberment table, which typically has results ranging from minor but flavorful to actual death and dismemberment.
• Another option is for a critical hit to provide an opportunity for another attack roll, perhaps repeated if the second roll also qualifies for a critical.  If used with the standard Natural 20 crit rule, it provides some of the advantages of both methods of determining whether a critical hit has occurred.  It's a relatively uncommon occurrence, and you've got to succeed at a second attack roll in order to capitalize on it, so characters with good attack probabilities do better, and targets with poorer ACs fare worse.  This one is the front-runner for my personal favorite.
• Yet another option is for stunts and special attacks called by a player to occur on a critical, as in the Simple Combat Maneuvers from Telecanter's house rules.  No extra damage, just extra possibilities.  Could be used in conjunction with one of the other options - if you don't call for the attack to do something cool, a natural 20 just defaults to the other critical hit option.
• Finally, exploding damage dice are also a critical hit mechanic of a sort, which operates independently from the attack roll, and instead is activated by rolling the maximum on the damage dice.  Each time the maximum is rolled, the dice are rolled again and the result is added to the total.  This increases the average damage by a fairly trivial amount, but with a small chance to inflict a lot more damage than the weapon's usual range.