There are two levels of label removal: the first is to do a Remove label (File menu) on an object, the second is to remove a label that is no longer assigned to any object from the database. To do the latter remove log in as administrator, select the project you want to remove the labels from, and select Clean up project from the File menu. This will open the Clean up window. In this window you can opt to remove Unused labels.
Labels are directly removed from the database and cannot be restored.