How does Chakotay get his medicine bag back in "Initiations" (season 2, episode 2)? He had it in the shuttle that was destroyed.
At 22:32 you see Torres receiving various samples from the "debris field" of the destroyed shuttle. Although we don't explicitly see the bundle being recovered we do know that Voyager is very keen to avoid their technology falling into the hands of the Kazon and would have transported every part of the debris back on board.
Since we see the bundle again a few scenes later (apparently unscathed) there's no special reason to assume that it wasn't simply found floating in space with the other remnants of his ship.
From an out-of-universe perspective, the show's Prop Master seems to have reused the same leather chamois to cover the medicine bundle in both scenes. As you can see from the picture below, there are several heavy folds that are in the same place on each of the bundles. If it was replicated, then it was a masterful copy.
Chakotay kamikaze'd his Maquis ship into a Kazan dreadnought during the first episode of Voyager, being beamed away only at the last moment. As in the season 2 episode where he lost his shuttlecraft, he didn't have time to gather personal effects before he left. So this was at least the second time Chakotay had lost his kit. So he could only have assembled a new medicine bundle after each loss, either from replicated items or things he found on away missions in the Delta quadrant.