Header Menu Not refresh each time

Need some technical approaches such that the menu system that appears across client website should not have to refresh/reload each time a page is visited.  This is because the menu system will not change and thus, its a waste of bandwidth and performance to have this loaded for each page visit.

However, keep in mind that the Messages icon should allow for call back to the backend to determine if users have new messages upon page refresh (so I guess in some ways the Messages menu item will be dynamic, and the rest of the menu system shall stay static). So could you please help me how can I do this.If this is possible with cache then which one is better Post Cache substitution or Sql Cache.

Thanks