If you are using a JIT, configurable extension, be aware that 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);

        }