1. Make sure your add-in is installed correctly and it is enabled
Open registry editor and navigate to “http://support.microsoft.com/default.aspx/kb/291392”. Here is how this registry key looks like after I installed MyExcelAddin:

The registry string we are interested in the most is the LoadBehavior. Whenever you see "3" (Loaded at Startup) as the value of this string you are good in this part and your add-in tries to load when the Excel starts. For more information about registry entries for application-level Office solutions see http://msdn.microsoft.com/en-us/library/bb386106.aspx.
2. Check out “COM Add-Ins” dialog in Excel
Now open Excel and see if your add-in loads successfully. If not, open Excel Options dialog (File->Options) and navigate to Add-Ins tab.

“Healthy add-ins” show up as “Active Application Add-ins”, however, if an add-in is disabled for whatever reason, it will appear under the “Inactive Application Add-ins”. You can select the “COM Add-ins” from the Manage dropdown at the bottom of this dialog and see the LoadBehavior of all COM add-ins. In normal cases, the add-in should be checked and its "Load Behavior" should be “Loaded at Startup”:

If the VSTO runtime encounters a problem loading the add-in, you’ll see this message instead.
“Load Behavior: Not Loaded. A runtime error occurred during the loading of the COM Add-in”.
3. Find the problem
Set the "VSTO_SUPPRESSDISPLAYALERTS" environment variable to 0. Then go back to the registry key I mentioned in step 1 and set the LoadBehavior to 3. Now restart the Excel. You should be able to see a dialog describing what is happening:
It is also a good practice to enclose the code inside the add-in's startup event in a try-catch block and log all exceptions.
4. Hard disabled add-ins
If an add-in causes the Office application to crash (close unexpectedly), the add-in gets “hard disabled”. Please follow http://msdn.microsoft.com/en-us/library/ms268871.aspx instruction to re-enable the add-in. In addition, you might want to check the “HKEY_CURRENT_USER\Software\Microsoft\Office\12.0\Excel\Resiliency\DisabledItems” (replace 12.0 with 11.0 for Office 2003 and with 14.0 for Office 2010). Your add-in should not have an entry under this registry key.
More References:
-
http://msdn.microsoft.com/en-us/library/ms269003.aspx
-
http://blogs.msdn.com/b/vsod/archive/2008/04/22/troubleshooting-com-add-in-load-failures.aspx
-
http://blogs.msdn.com/vsto
-
http://social.msdn.microsoft.com/Forums/en-US/vsto/threads