The paleo diet is an attempt to emulate the diet of our Paleolithic ancestors, with whom we share 100% of our genetic makeup. Our bodies aren't made, the story goes, to live on grains or legumes (rice and beans, EREs!) but rather on animal/fish fat and protein, a moderate amount of vegetables, some starches, coconuts, and a tiny amount of fruit and nuts.
There are many variants on it, but, contrary to the capital-P Paleo Diet book by Cordain, most contemporary "paleos" get 40-80% of their energy from fat, largely saturated fat from meat, fish, eggs, butter, coconut oil, coconut milk, lard and tallow, and they eat 0-150 grams of carbs per day (compare to 350+ for most Americans). There are raw-only paleos, zero carb paleos, triathlon paleos, and so on, but you won't find any of them eating breakfast cereal or other low-nutrient foods such as rice, bread, pasta, white potatoes, or energy bars, nor will you find many eating mounds of fruit or nuts at a sitting.
@Q: There's nothing wrong with eating more than once or twice a day. However, there is mounting evidence of long-term health benefits in "intermittent fasting." If you've heard of the effect of calorie restriction on longevity in animal studies, it turns out there is similar benefit from "IF." As you may have read, Jacob does the Warrior Diet, which is one decent/large-sized meal at the end of each day--it's very likely that our ancestors ate in this manner: Wake up; hunt; carry the kill back home; eat. When eating a paleo diet, over time it becomes very easy to, without thinking about it, go for 7+ hours between meals, or 15+ hours overnight. If your diet is made largely of vegetables, tomatoes, rice, beans and white potatoes, however, I think it would make it much harder to do IF. (how do you do it, Jacob?!)
Some credible resources:
http://www.paleonu.com/
http://wholehealthsource.blogspot.com/
http://www.paleohacks.com
And: I discovered paleo via marksdailyapple.com. I think he's very credible and a good resource too, despite the fact that he hawks his own nutritional supplements on the site.
Some NYC friends who are current/future luminaries and bloggers of paleo (John was on the Colbert Report earlier this year):
hunter-gatherer.com (John Durant)
huntgatherlove.com (Melissa McEwen)
@Catherine - I'd love to talk on the forum with you about the environmental aspects of vegetarian/vegan vs. paleo. There's actually quite a bit of debate about it, and there are a number of ex-vegans in the paleo community. I'm also concerned about my ecological footprint, and I foresee that footprint shrinking dramatically when I start hunting white tail deer, whose population is out of control on the east coast, instead of buying expensive grass-fed beef/pork/lamb, as I currently do. Also, soy is regarded pretty much as poison among paleos--not to alarm you, but you might want to read up on it on some of the aforementioned sites. Intermittent meat consumption--from observation of modern-day hunter-gatherers, I'm not sure this is accurate. For example, Native Americans made and ate jerky and pemmican, thereby preserving meat for steady consumption.
@Jacob: I have not personally done an every other day fast, but other, more experienced paleo followers do it as a matter of lifestyle. The idea of IF is to "accidentally" do it because your glucose/insulin is so steady and your fat metabolism is so efficient that you don't feel hungry for hours and hours.
There's a whole exercise side to paleo as well, which I won't go into here, because this post is already long... Would also like to discuss the ever-important budget aspect--my food budget is currently $350, and I see it going down to $160 only upon extreme early retirement (in five years). Finally, I haven't said a thing about the actual science of it, involving inflammation, insulin, fat metabolism, etc. (see resources above, and perhaps we can discuss)