If a player playing with infect loses the game are the poison counters they have dealt out removed, similar to how curse enchantments they own would leave the game. Or do they remain, similar to how a -1/-1 counter on a creature would stay?
They remain on the player who has them. Counters are not owned by the player that created them, they just are there once created and are not removed unless an effect specifically says to remove them. That means that even if only one player is using infect and is removed from the game proliferate can still cause another player to lose due to poison.
There is only one thing in magic that actually removes poison, the card Leeches.
A new game started with Karn Liberated will not keep the counters a player had when the new game begins. These counters, like everything else in the original game cease to exist.