Exactly, each copy of the game had this soundtrack CD enclosed in a form of physical release.
I personally, don't know about any other way it might have been available back in time. When checked old, now defunct website, there's also a mention about strictly limited game release only.
Not having mine around right now, but picture can be seen here:
http://ceskehry.wz.cz/obaly/paranoia2all.jpg
Enclosure description fits much better than Promo/Gift/Reward based on info provided in step-by-step guide.