If you find the note at the rig and talk to Knuckles and say the right things, he reaches into a small crevice in the wall and pulls out the cigars. Afterwards, the crevice is a container and has a couple other things in it. I think the crevice should be a secret/perception check to find, albeit a very high one (more than 11 at least). I just tested it with an imported character, killed Knuckles and co, then got to 20 effective per and still couldn't find it.
