The cannibals inhabited island, Pelegosto, a jungle island in the Caribbean. They believed Jack Sparrow was a deity trapped in human form, in which they must release him by eating his body. They are secondary villians in Dead Man's Chest, and are mentioned in The Curse of the Black Pearl.
In The Curse of the Black Pearl, Jack Sparrow remarks, "and then they made me their chief", revealing that he had been to the island previously.
In Dead Man's Chest, Jack Sparrow beaches the Black Pearl on Pelegosto, knowing he was being hunted by the Kraken. The cannibals ate half the crew and with their bones, made spherical cages to imprison the rest. They once again make Jack their chief and tie him to a spit ready to roast him on a fire. He escapes the village when the cannibals chase after the crew. Jack is reunited with the crew on the beach, where they narrowly escape the cannibals. The tribe spot the prison dog on the beach and chase after him.
The cannibals make the dog their new chief, however, like Jack, he manages to escape the island.