Apparently Karlach boarded the nautiloid when it went through Avernus, got captured and implanted while it was there, and hitched a ride out with it. Which honestly sounds like a lie, because that would require a lot happening in a short stretch of time. Like, probably 30 minutes of time in-world. We know she already has a tadpole, but the idea that she got specifically captured and implanted so quickly seems questionable. Unless you subscribe to the theory that true souls are hand picked and they were in Avernus specifically to implanted her.