The paleo diet could definitely be done on the trail using foil packets of tuna, chicken, & salmon as well as large amounts of nuts & dried fruit & veggies.
I've found that eating small meals like larabars, dried fruit, or almonds about every 1.5-2 hours helps me maintain my energy levels while hiking and running. if I don't eat this often, I notice my energy waning. I agree with Dean Karnaze who suggests many small meals throughout the day. I apply that principle with my snacking and also have a set breakfast, lunch and dinner that is more than just a few handfuls of almonds or an energy bar.
My hiking diet is similar to the paleo diet in that I eat a very large amount of nuts, dried fruits, and larabars (which are essentially more nuts & fruit) as well as some tuna and chicken - however I DO include complex carbs in my diet via pasta, bread, rice etc. Most runners do (including Dean K.) I apply the same principles to my hiking diet. Carbs are a great source of fuel for your body. If you have a lean body and are expending a lot of energy and burning a lot of calories on a regular basis, you need that fuel. I disagree with the premise of the paleo diet there. I don't think rice, pasta, and grains should be cut out of a diet.
The purpose of my diet while backpacking is never to get more lean. It's to maintain my glucose levels and promote energy, endurance and muscles recovery as much as possible. I can't quite tell if you are interested in losing weight or just in being as healthy as possible while hiking. The same puzzlement applies to Hufeza's diet concept as well. Essentially, I agree with what Chad is saying and feel that the paleo diet excludes an important aspect of nutrition for an athlete. If you are looking to lose weight, I think the paleo diet is healthy and is a good idea and is indeed doable while hiking. If you are looking to expend the amount of energy that an endurance athlete is - i.e. a long distance hike, extended periods of high mileage etc. - I question excluding grains & beans (and even certain nuts, correct?) to that extent.
This explains my diet pretty well, see the link at bottom for source:
" All of the popular weight-loss plans that recognize the difference between low GI and high GI carbohydrates strongly recommend eating low GI foods to maintain your weight and health. But things aren't that easy for runners, who need to include a mix of both high and low GI foods in prerun and postrun meals in order to get maximum performance benefits. That's because high GI foods can help boost speed and aid in recovery, while low GI foods extend endurance.
Not all carbohydrates are created equal. Some provide your body with a slow and steady stream of energy, while others deliver fast but short bursts of fuel. The difference between these two types of carbohydrates is something called the glycemic index (GI).
The GI is a carbohydrate ranking system that assigns a number from 1 to 100 to a food based on how quickly the carbohydrates in it enter your system. If the carbs are quickly digested, with sugar rapidly entering your circulation, the GI is high: 70 plus. Many complex carbohydrates such as breads, pasta, and potatoes have moderate to high GIs.
If your digestive system has to wrestle with the carbs a bit before the sugar makes its way throughout your system, the food's GI is low: less than 55. Most fruits and other fiber-packed foods such as beans and old-fashioned oats have a low GI, because the fiber trips up the sugars before they are absorbed into your system.
The addition of fat or protein also changes a food's GI. Both of these nutrients slow digestion and, therefore, lower the GI of a food or meal. So, a slice of wheat bread topped with peanut butter has a lower GI than the bread alone."