There have been several newsgroup postings about using VSTO to create Visio Add-ins.  The deployment of these add-ins can be especially challenging.  There is a new developer article by Chris Castillo detailing how to write VSTO add-ins for Visio.  Chris explains why using VSTO is desirable and aggregates information from a number of sources to walk you through the development and deployment process.

http://blogs.msdn.com/chcast/archive/2007/03/28/creating-visio-add-ins-with-vsto-2005-se.aspx.