user permission cache in session or check from database?
For maximum performance, caching (i.e., precomputation) is pretty much a requirement. Unfortunately, though, there's no cookie-cutter answer for how to implement it. It's not as simple as picking either solution x or solution y.

What you want to do is come up with a strategy that caches the information you need as close to the request for the information as possible, while still meeting the business requirements and staying within the architectural limitations (which, by the way, you may want to change to encourage the use of caching, not only for this, but for other areas, too).

Here are a few factors and some questions related to each to get you started thinking about how best to implement this for your own scenario:


The application architecture. Are you using a caching tier? Are user sessions sticky on the web tier, or is it round-robin? (Should you change this?) Are there any other applications accessing the database for the same security information besides this particular web application?
The requirements for the application. Should changes to the security permissions take effect immediately (i.e., on next page load), or is a delay acceptable? How long a delay? Immediate effects generally limit our ability to use caching to its maximum effectiveness, but that's definitely not to say it's infeasible to cache at all.
How expensive it is to compute the required information? Will it be computed on-demand, or proactively when the underlying data changes? Synchronously, or asynchronously? Caching can be introduced within the database itself, which alone may be enough to satisfy the immediate performance requirements.
How frequently will the information be needed? You say it's needed for every page on the site, but what does that mean in terms of requests/sec and overall server load? Could the mechanism this information is retrieved by be optimized further?
How frequently will the information be changing? Since you're asking about caching at all, I assume it doesn't change frequently, but that could be a bad assumption on my part, so I'm mentioning it. If the information changes frequently, pay particular attention to the performance of the cache invalidation strategy you put in place.


As I eluded to, there are multiple opportunities and configurations for caching in this scenario, using any combination of: the data tier, the web (application) tier, and the caching tier (if applicable). Of course, the more levels of caching you do, the more complex the environment and codebase becomes, so you definitely want to watch out for that.