The Paleolithic ('Paleo' for short) diet is based around the premise that the human body is healthiest eating the same sort of pre-agricultural, hunter-gatherer-style diet that was eaten for most of human evolution. There is no widely accepted scientific evidence to support this premise.
Modern 'paleo' diets generally make concessions to the modern environment rather than being a strict recreation of a particular pre-historical diet, but embrace the same principles.
A paleo diet focuses around lean meat (ideally game meat), vegetables and fruit and a small amount of nuts and seeds. Specifically excluded from the diet are dairy, grains, sugar, salt and (of course) highly processed modern food products such as cheese puffs.
The Paleo diet shares some characteristics of low-carb/high-protein diets such as Atkins but is more focussed on what is imagined to be eating in a historically "natural" way. It also contains lower levels of fat (and particularly saturated fat) than many low-carb diets.