How does adding baking soda to soaking beans/lentils reduce the gas they make you have?
Summary: Baking soda is mostly used to soften the beans faster and decrease cooking time by increasing pH.  In some scenarios, it has been shown to aid in breaking down gas-causing sugars as well.  Higher concentrations of baking soda and/or pressure cooking may be needed to make this latter effect significant.  In most cases, an increased soaking time will have a much greater impact on gas-causing sugars, so baking soda should perhaps be reserved for situations where preparation time is limited.



Baking soda isn't primarily added to reduce gas.  As pointed out in previous responses, it can use its sodium ions to replace the magnesium in the cell walls of plants, resulting in faster softening.  However, this can also be done with the addition of regular table salt.

The reason baking soda in particular is often added to bean recipes (either during soaking or during cooking itself) is that it makes the beans slightly alkaline, which increases the softening effect.  As Harold McGee says in Food and Cooking, "Acidic cooking liquids slow the dissolving of cell-wall hemicelluloses and therefore the softening process, while alkaline cooking water has the reverse effect."  He further recommends:


  Baking soda at 0.5% (1 teaspoon/qt) can reduce the cooking time by
  nearly 75%; it contains sodium and in addition is alkaline, which
  facilitates the dissolving of the cell-wall hemicelluloses.... The
  alkalinity of baking soda can give an unpleasantly slippery mouth feel
  and soapy taste.


The softening of the cell walls will allow faster breakdown in some of the sugars with cause gas.  Scientific research showed this effect of alkaline substances like baking soda on beans and legumes many decades ago, dating back at least to the early 1970s.  Unfortunately, most of this research is only available in obscure food journals, but this free article gives a sense of common findings (here regarding Seker beans).  As for the mechanism, they offer:


  Ku et al. (1976) noted that soaking in the 0.5% sodium bicarbonate
  solution might increase softening of the testa [seed coat] and cotyledons [interior of bean] that
  could increase the sugars extraction.


Ultimately, the combination of an 18-hour soak in the baking soda solution followed by cooking in a pressure cooker achieved the highest reductions in gas-causing sugars (up to 70%).  (Pressure cooking also destroys these sugars more effectively than conventional cooking.  Also, note that, unlike McGee's advice, they rinsed the beans after soaking and used fresh water for cooking.)

While baking soda speeds cooking and can reduce flatulence, it also has negative impacts on nutrition.  Ku et al. (cited above) noted protein destruction when cooking tripled when baking soda was added.  But the more significant concern is B vitamins.  Again from the Seker bean article:


  [A]lkali condition may cause further destruction in the Vitamin B
  contents, especially thiamin and riboflavin (Swaminathan, 1974). 
  Therefore tap water might be a good alternative to protect vitamins
  and have a moderate decrease for the flatulence factors.


And actually, it's important to note that pressure cooking had a very significant impact on how effective the baking soda solution was.  Assuming an 18-hour soak, the following reductions in gas-causing sugars were seen on average:


Plain water soak, pressure cooking: 51% reduction 
Baking soda soak, pressure cooking: 69% reduction
Plain water soak, normal boiling: 48% reduction
Baking soda soak, normal boiling: 51% reduction


Baking soda thus barely had a significant effect in this study without pressure cooking.  Other studies have also seen the effect of baking soda affected by cooking method, but elements such as soaking time may play a role as well.  This study, for example, measured statistically significant decreases in gas-causing sugars due to baking soda in five other bean types under almost all types of preparation conditions (6-hour soak vs. 12-hour soak, soaking alone vs. boiling vs. pressure cooking, sprouting for 1-4 days, etc.).  However, in almost all preparations the sugar contents were only decreased by a few percent with baking soda.  (Even pressure cooking did not change this in most cases.)  Only one sugar, raffinose, was reduced by more, in some types of beans achieving an additional 5-14% reduction with baking soda.

However, the important finding to take away from these studies is the relative importance of the various parameters.  In order of effect, they are:


Length of soaking (or germination, for even greater effect)
Pressure cooking, instead of simmering
Adding baking soda


For almost all scenarios, it appears that soaking for an extra few hours, doing a 24-hour germination before cooking, or choosing to pressure cook beans will have far greater impacts than adding baking soda.  Moreover, extended soaking or germination tend to actually release more nutrients from the beans as various enzymes break down indigestible substances, rather than destroying some of the nutrients as baking soda can.  Other studies have suggested that long cooking will also break down gas-causing compounds more quickly than soaking could do.  Thus, in some circumstances, an extended low simmer with no prior soaking might achieve a greater reduction than a brief soaking period with baking soda.  (The baking soda might even be counterproductive in this case, since it would soften the beans faster and not allow a longer cooking period.)

In any case, most of these studies have assumed a rather significant amount of baking soda during soaking (generally around McGee's recommendation of 1 tsp/qt), since the pH must be increased significantly for the baking soda to have effects.  Adding only a "pinch" may have only a negligible impact, particularly if the beans are only boiled and not pressure cooked.

Moral of the story (again): While baking soda does something in reducing gas, the effect is generally quite small.  Use it primarily to speed up cooking or soften beans instead.