In order to apply a label to a contact, just click on the contact in question and open the contact details page. From here you can apply or remove labels by clicking on the label icon and clicking on the labels you wish to apply or remove. Changes to labels get saved automatically.

If the contact is only linked to one claim you will be able to also apply/remove labels by viewing the contact from within the claim.