Are you using a JIT, configurable extension? JIT extensions only startup when they are called.
Regular extensions should startup together with ArcMap (wether they are configurable or not - I need to confirm this, can anyone help?)
Just-in-time Extensions
Extensions are generally loaded when an ArcGIS application first starts up. For example, in ArcMap the extension manager instantiates each extension it can find in the ESRI Mx Extensions component category and calls its IExtension::Startup method.
You may want to develop your extension to be a just-in-time (JIT) extension. The concept behind JIT extensions is to avoid creating objects until necessary; therefore, ArcMap does not start up a JIT extension until it is actually required.
http://edndoc.esri.com/arcobjects/9.0/ExtendingArcObjects/Ch03/AboutExtensions.htm
The greatest difference between them is how you register the extension. They basically implement the same interfaces. To sum it up, check the category your extension is registerd in. See the ArcGISCategoryRegistration method in your extension:
// common extension, starts up when arc map starts
private static void ArcGISCategoryRegistration(Type registerType)
{
string regKey = string.Format("HKEY_CLASSES_ROOT\\CLSID\\{{{0}}}", registerType.GUID);
MxExtension.Register(regKey);
}
// JIT extension, will only start when you first call it
private static void ArcGISCategoryRegistration(Type registerType)
{
string regKey = string.Format("HKEY_CLASSES_ROOT\\CLSID\\{{{0}}}", registerType.GUID);
MxExtensionJIT.Register(regKey);
}