When I create add-ins that have toolbars I always add the custom
toolbars at that time, and remove them in the Workbook_AddinUninstall
event.

I notice that most other addins (EssBase, MS Add-ins) don't do it this
way. The toolbars get added each time the add-in is loaded via the
Workbook_Open event.

Is there some type of common practice that should be used?

Is there some reason why you should choose one over the other? It seems
to me that by using the Workbook_open event it takes longer to load
Excel.