To remove a web part:

1. On the Web Part Gallery page: click the 'Edit' icon that is next to the web part
2. On the Web Part Gallery: click Delete on the <your web part> page. Then click Ok.

If you remove a part from the gallery, it will no longer be available to users to add.  Parts that are already being used WILL still work.  But, if an admin removes the web part's assemblies on the server the existing parts will no longer run.