L Olsen:

TPM is indeed a good overview of all the aspects of Paleo.  The diet gets the most press, but the other aspects are also very important for good health.

If you're looking for more detail on the science behind the Paleo dietary recommendations, and on the variants thereof, you'll want to read something like Perfect Health Diet.

It's not really possible to eat Paleo and still be a strict vegetarian, though it is quite possible to eat a grain-free vegetarian diet.  However, if by "vegetarian" you actually mean "pescetarian", which many people do, a fish and shellfish-based Paleo diet is quite doable and very healthy!  (Though it can get expensive...)

JS