If every user will get the same menu:
You should consider putting it in the Application "Cache" - Application["MyMenu"] or a static field on one of your objects.
The main reason for this is lifetime. If you put it in an application level object, then it will last for the lifetime of the application. Putting it in a session level object will cause it to be lost when that session ends - as a session is started per user, then you will soon find yourself recaching the data.
On the other hand... if it's unique per user:
The session provides a handy place to put this data, as it is unique to that user, and will not live long beyond that user leaving the site.
Also think about:
If you really think memory is going to be an issue or you want to define exactly how long you keep it for
Put it in the Cache. You can determine the amount of time it lives in the cache, and, additionally, the cache will start to dump objects when it gets short on memory - so it is more sensitive to load than the other options.
There is a good discussion of Session vs Cache on SO already
Additionally
Are you sure your menu is that big? If it is, you might want to consider alternatives - just how big are you talking?