I have an AdminMenu model that defines my admin system navigation hierarchy. This is the same for all users. The structure is cached after every save to it. When a user logs into the Admin system, I fetch the menu data from the cache and also fetch all permissions that logged in user has been granted access to. I do this in a single query. The details are posted here.
I then recursively iterate through the menu data, checking each node against the permissions for that user, and build up a menu structure and store it in the session. This menu structure only contains the nodes the logged in user has permission to access, and it's only generated once, when they log in. This menu structure is then rendered with a helper.
In addition, the permissions are available in the session, so you can check whether to display links in your views or not, e.g. only display the link to delete a post if they have permission to delete it.