There are 257 heads required required for the achievement, consisting of all the heads in each of the four basic head shapes, and the plain Star head. The rest of the star heads are special and obtained from proms, and don't count towards the achievement. When starting the game, every player will start with one additional random head of each of the four different head shapes. Prisoners initially cost 10 gems each, but the price will gradually increase by 5 gems until they cost 30 gems a piece. The total number of gems to unlock every prisoner solely from the venting machines is close to 4500. Gotta catch em all.
Even after completing the story in all four modes it is unlikely that you will have enough gems to buy all of the heads. Replaying levels to get the A++ will earn you two bonus gems in addition to any gems you missed before. Another ten gems are earned for carrying a randomly occurring Golden Hat to the exit. Gems can also be earned in 'Furbottom's Feature,' which has a single player and a co-op chapter that changes every other week. Finally gems can be earned in the arena mode. Four gems for a win, one for a loss and a bonus gem for the MVP(Most Violent Player.)
The fastest way to earn gems to to grind arena matches offline with a dummy controller, then set up a game of muckel, once the game starts kill your dummy once and then let to two minutes run out. Repeat as necessary. This will earn you five gems per game, four for the win and one for the MVP(most violent player) bonus. Additionally the dummy will earn one gem per game, these can then transferred to the main using the trading booth (Make sure dummy account is not a guest, or the game will not allow you to trade).
Here's a chart from the Behemoth that shows all of the regular characters in the game: