By default, deleted contacts are sent to the trash, and may be recovered at a later date by an administrator (or anyone holding the "access deleted contacts" permission"). To restore these contacts, go to Advanced Search, enter the contact’s details and check the Search in Trash check-box at the bottom of the Basic Criteria section.
From the list of results, you can either recover contacts individually using the Restore link at the end of the row, or by choosing Restore contacts from the action drop-down menu.
If you are sure that you no longer have a need for the particular contact, you can delete them permanently.
Note that you can disable the trash function if you like in Administer > System Settings > Misc (Undelete, PDFs, Limits, Logging, Captcha, etc.)