One of the more accessible (and less dogmatic) approaches can be read here:
There are many varieties of the Evolutionary Eating idea, so a strict definition of "this is PALEO" will be hard to come by.
http://www.paleonu.com/panu-weblog/2011/3/30/paleo-20-a-diet-manifesto.html is a good view as to what the Paleo movement may be evolving into....
I'm pasting an answer here that I wrote for Paleohacks.com in regards to which BOOK was a good first introduction to Paleo.
It really depends on the learning style and history of the targeted reader.
They are just looking a solid approach in an entertaining (tough-loveish) format?
Robb Wolf's The Paleo Solution: The Original Human Diet
They have a science-minded bent, but just want the overview? Gary Taubes' Why We Get Fat: And What to Do About It
They have a science-minded bent, but want all the details? Gary Taubes' Good Calories, Bad Calories: Fats, Carbs, and the Controversial Science of Diet and Health
They need the friendly, easy access version. Mark Sisson's The Primal Blueprint: Reprogram your genes for effortless weight loss, vibrant health, and boundless energy
Personally, I started with Sisson's work and website, and then dove into GCBC and loved it... but I'm a huge science geek.
I would give Sisson to my ( not steeped in science ) relatives, and I would would set the rest up with Taubes' Why We Get Fat.
Make sure to tell them that this is the first stepping stone, and the start of a great journey.