Perhaps something went wrong in the Add-In installation process?
It sounds like you've already looked at this, but if not, check out this page for the actual Add-In Installation:
http://resources.arcgis.com/en/help/main/10.1/index.html#/Testing_an_add_in/014p00000026000000/
You may have to (in ArcMap), go to Customize -> Add-In Manager. There, you should see your Add-In. If it has it's own toolbar, then click customize and make sure your toolbar is checked so it'll show up.
Did you specifically create a toolbar for your add-in, as well as a tool (or button)? If not, open the customize window, and select the "commands" tab, and type the name of your tool in the "Show commands containing" box. If your tool installed properly, regardless of whether it is part of a toolbar, then it should be there. You can then drag the tool and place it in any open toolbar.
Kerry