In most 1st edition groups I was familiar with, falling damage was computed by the UE method, that is 1d6 per 10' cumulative (a fall of 30' was 6d6). Some groups also played 2d6 per 10' (a fall of 15' was 3d6, and a fall of 30' was again 6d6). Max damage tended to be 30d6 (roughly 105 damage on avg.), so that an infinately long fall had a good chance of killing most high level characters. (Early published modules stuck to 20d6).
I don't believe Gygax's assertion that this was the way it was played in his campaigns all along. As has just been pointed out, all of his classic modules treated damage in a linear fashion. For instance, in 'Tomb of Horrors' a fall of 30' was 3d6. Of course, back in those early days there seemed to be nothing like consistancy in the rules. In the same module, a fall of 100' does 10d10 damage. I suspect that Gygax adopted the 1d6 cumulative rule sometime between the printing of the DMG and UE, much as many groups had already done, and probably for the same reasoning. Falls of great distance didn't have much chance of killing mid to high level PC's. This has always been a source of concern for those that like realism.
Since converting over to 3rd ed. I've modified my house rules further, so that a falling creature subtracts its AC modifier due to size from each dice of damage. In this way, diminutive creatures realisticly take minimal damage from falls. A fall of 20' would do them 3d6-12 (avg. 0), whereas the same fall for a large creature does 3d6+3 (avg. 14). The bigger they are, the harder they really do fall. In real life, a mouse will probably survive a fall of 80' (or indeed a 1000') without serious harm, and a cat (a tiny creature) will probably live though be seriously injured. To take this into account, I'm considering adjusting the terminal velocity (measured in dice) for creatures of different sizes. For instance, maybe limiting diminutive creatures to 3d6, tiny to 5d6, small to 20d6, but large to 40d6, huge to 50d6, and so forth. I'm a little worried about play balance since small PC's (unrealisticly) have the full Con of medium sized ones, but its alot more realistic to scale damage from a fall to size. If a Cloud Giant falls because Jack cut down his beanstalk, he takes 50d6+100 damage (as a opposed to the 20d6 he'd otherwise take). Splat!
Although I've never used it, I also like the rule from Dragon that smetzger quoted because it nicely maintains the danger of heights while allowing characters to normally get away with just bruises:
"1d20 for every 10 ft divided by 1d6. So a 30 ft fall would be 3d20/1d6. With a mean of 9, minimum of 0, and maximum of 60."
While we are on the subject of falling, for the sake of elegance, the damage a falling objects does ought to be comparable to the damage it suffers from falling. The realism of the above rules I think really sticks out when we start use them to try to figure out roughly how much damage is inflicted by a falling object. We only need make a few modifications to take into account density compared to an average living creature. First we start by figuring the size of the object based on its weight (there is a handy table in MM1). Then we decrease its effective size by 1 if it is not dence (a pillow), and increase it by one if it is either highly dence (a brick) or aerodynamic (a dart or a bead) or by two if it is both. Finally, we increase the base damage by +1 per dice if it is sharp, +1 per dice if it is unusually hard, or -1 per dice if it is unusually soft.
For the two examples given, a 1 lb. pillow is a soft non-dense Tiny object, and therefore after a long fall does 3d6-15 damage (to what it hits and to itself assuming it doesn't hit another pillow). A dart is a sharp, dense, aerodynamic, fine object, and is therefore treated as a tiny object doing +1 damage per dice, or 5d6-5 (avg. 13, 8 to itself) after a sufficiently long fall. If the dart were tumbling (not aerodynamic), then the damage would be only 3d6-9 with 0 damage indicating a glancing blow.
Some other examples: a falling 6 lb. sharpened steel spike is a hard, dense, sharp, aerodynamic, tiny object and after falling 20' does 3d6+6 damage. A piano is a large object and therefore inflicts 40d6+40 damage after a fall of 90' or more. A 1 ton block of stone is a hard, dence, large object, and therefore does 50d6+150 damage after a fall of 100' or so. Splat! (Much more satisfying than righting 'instant death, no save', especially since some collosal creatures would survive this.) A reflex check to avoid (or take 1/2 damage) is I think appropriate in any of the above cases (assuming that the character can see and has somewhere to jump).
At the ridiculous end of the scale, a 250,000 lb. asteroid slams into the ground doing (very conservatively) 80d6+720 damage. I'd suspect that the CR for a trap with that for the effect might exceed the normally recommended limit of 10 by some ammount, but I'm not in to 'Epic Level' campaigning.