The Web Part definition files have to be in the Web Part Gallery in order to be available in the "Add Web Part List".
You can create a SharePoint site feature to deploy the definition files in this library:
feature.xml:
<?xml version="1.0" encoding="utf-8" ?>
<Feature
xmlns="http://schemas.microsoft.com/sharepoint/"
Id="DFD20610-C329-45E0-B037-8E6FC0A684AB"
Title="Web Part Feature"
Scope="Site"
>
<ElementManifests>
<ElementManifest Location="Elements.xml" />
<ElementFile Location="TheWebPart.dwp" />
</ElementManifests>
</Feature>
Elements.xml:
<?xml version="1.0" encoding="utf-8"?>
<Elements xmlns="http://schemas.microsoft.com/sharepoint/">
<Module Name="WebPartPopulation" Url="_catalogs/wp" RootWebOnly="TRUE">
<File Path="TheWebPart.dwp" Url="TheWebPart.dwp" Type="GhostableInLibrary" IgnoreIfAlreadyExists="TRUE">
<Property Name="Group" Value="Custom" />
</File>
</Module>
</Elements>