Can/should I use baking soda when cooking beans?
In his book On Food and Cooking, Harold McGee writes regarding beans and legumes:


  Plain salt at a concentration around 1% (10 g/L, or 2 teaspoons/qt)
  speeds cooking greatly, apparently because the sodium displaces
  magnesium from the cell-wall pectins and so makes them more easily
  dissolved.  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.


Basically, you are right that sodium is important, so both salt and baking soda will have effects that speed cooking.  (The idea that salting toughens beans or makes them harder to cook has been covered in another question; brief summary -- it's a myth.)  Baking soda is even more effective than salt, because it produces an alkaline cooking liquid.  Acids slow the cooking and softening of beans, while alkaline solutions will hasten it.

The main drawback of baking soda is that it also affects the taste and texture (as McGee describes it, "an unpleasant slippery mouth feel and soapy taste").  Also, the effects that lead to a faster breakdown of the beans for softening can also result in destruction of a lot of nutrients, as I discussed in detail in a response to a related question on baking soda, beans, and gas.

To me, the drawbacks of baking soda are too great to justify its use unless I had an emergency situation and had to cook beans very quickly.  But it can in fact decrease cooking time significantly, so it can be very effective for that goal.