These soaps are simply soap-shaped lumps of stainless steel. You'd get the same results from rubbing a spoon on your hand, or rubbing your hands on the sink.
There's a ton of anecdotal evidence that stainless steel works; unfortunately there seems to be very little scientific evidence backing it up. I've never read any in the past, nor was I able to find anything convincing while researching this answer.
Various explanations abound but should all be treated as speculation until some hard experimental data comes out:
About.com's Chemistry Ph.D thinks it's a chemical reaction with sulfur, but admits that it's speculation. I find that explanation dubious at best, because the whole point of stainless steel is that it's non-reactive, and not all of the odours that S.S. supposedly removes are based on sulfur.
Another cooking blogger references McGee and postulates that it might be due to static electricity, which is sort of corroborated by the Straight Dope's hypothesis of ionization. Follow-up comments to the former entry dispute his claim, as well.
Finally, the Straight Dope link above also suggests that the metal might simply be acting as an abrasive. This, to me, is the most plausible explanation, but there's still no specific evidence supporting it. Again, if you care about anecdotal evidence, someone did a little experiment on SD's discussion board and claims that rubbing with anything works - it doesn't have to be metal - which supports the abrasive hypotheses. Then again, it's questionable whether the experimenter here actually impregnated the skin or just got a little scent on the surface.
So make of it what you will; nobody seems to know for sure why it works, but anyone who's tried it can tell you that it does work.
But don't waste your money on one of those "metal soaps" - just use a metal ladle, or the handle of a knife, or any other metal surface, and rub it on your hands under cold running water.