There is a blog posting on the DrEx blog that addresses the keys that need
to be created, in case you haven't already read it.
http://blogs.msdn.com/dr._ex/archive/2005/06/03/425099.aspx

So the question remains, how the heck do you actually make the registry
entries?

If you are using the MPF (Managed Package Framework) classes, there is a
class called Registration attribute.
(Microsoft.VisualStudio.Shell.RegistrationAttribute)

1) Derive your own attribute class from this attribute and implement
overrides of the Register and Unregister methods. The Register method is
where you write your values, Unregister is where you clean up after
yourself. Write your constructor so that it will take all the information
you need (like the category and service guids, etc)

using Microsoft.VisualStudio.Shell;
[AttributeUsage(AttributeTargets.Class, AllowMultiple = true, Inherited =
true)]
public class FontColorRegistrationAttribute : RegistrationAttribute
{ ....
public override void Register(RegistrationAttribute.RegistrationContext
context){...}
public override void Unregister(RegistrationAttribute.RegistrationContext
context){...}
}

The RegistrationContext argument is really handy. You call
context.CreateKey("FontsAndColors\\MyPackageName");
to create the appropriate subkey. The will correspond to creating a registry
key for you underneath the Visual Studio version hive.

2) Decorate your package class with this new attribute

[FontColorRegistration(..ctor params...)]
public class MyPackage : Microsoft.VisualStudio.Shell.Package

3) When the package registration tool runs, it will look for these
attributes, and invoke the Register method. That's it.

--Matthew