I investigated this question earlier today for an internal VS client and wanted to share the results with the rest of the world...
Your VS Package can place data into the solution file (.sln) or solution user options (.suo) file by implementing IVsPersistSolutionOpts (.suo affecting) or IVsPersistSolutionProps (.sln affecting). These interfaces should be implemented by the same class which implements IVsPackage.
The VS IDE will call these interfaces for each loaded package when a solution is opened/closed. If your package is not loaded when the solution is opened, then you won't be called to load your solution options. The remedy to this problem is to call the SVsSolutionPersistence service's IVsSoltionPersistence::LoadPackageUserOpts method yourself. This will cause the VS IDE to eventually call your IVsPersisteSolutionsOpts::LoadUserOptions method. The IVsSolutionPersistence::LoadPackageUserOpts method takes a IVsPersistSolutionOpts interface parameter which should be your package class pointer. You also specify your unique “keyname” when calling the method.
The above is true in VS7 and VS7.1.
In Whidbey the VSIP Managed Package Framework provides a nice base class (Package) implementing these interfaces and calling them for you. You simply call Package.AddOptionKey to add your unique keyname to the list of option keys the package handles. During the Package.Initialize() method the option keys are loaded using the above services/interfaces. You should call AddOptionKey during your package class constructor or any other method that is called before the base class Initialize() method.
The VSIP EnvSDK sample SlnExt is a great sample showing how to all of this in native code not using the managed package framework. I have designs to rewrite that sample to use the managed package framework, but for now that is left as an exercise for the reader.