After you deployed the solution package did you activate the Feature that adds your Web Part to the Web Part gallery (it will be in Site Collection Features).
This is done for you automatically by the deployment tools in Visual Studio but you need to do it manually when you deploy to production.
Path :==> Site Action ==> SIte Settings ==> Go to Site Collection Administration ==> select site Collection feature ==> where to active Your feature.
