It's quite easy to pull out of an MP3 if done correctly, or even shittier encodings, recordings etc.
Wiki seems to be lacking on info... Audio watermark detection - Wikipedia, the free encyclopedia
A company that does the embedding itself, and provides you with the watermarked copy is probably your best bet, as licensing the technology itself is extremely expensive, unless you've got some DSP programming skills, and are going to try and engineer something yourself.
A quick google for watermarking audio will start you down the path to confusion or enlightenment depending what you're looking for.
At the end of the day it is an extreme waste of time and money unless you really plan on checking leaks etc. for watermarks, and then enforcing/penalizing the offenders. Most labels I've worked with on the matter, don't even really do the follow up work except in extreme cases.
It's certainly not something for sales, usually more something used for protecting from leaks during early releases/review copies for press and such. If it turns out rolling stone keeps leaking it, well then you know who doesn't get a review copy next time. Again, pretty worthless unless you plan on penalizing offenders which can be difficult.