How do you implement deletion auditing?

First you need to enable the auditing of object access. This is set as a local policy, either in the local machine policy or it can be applied through a GPO. If you only sucessful ecents logged then you only need to enable the auditing of sucess.

Once this is done you can then specify which files/folders to monitor and which users you will audit.
If you configure a group policy to enable the Audit Object Access option, you can set the level of auditing for individual folders and files. This allows you to control precisely how folder and file usage is tracked. Auditing of this type is only available on NTFS volumes.

You can configure file and folder auditing by completing the following steps:

Once you audit object access, you can use the Auditing tab to set auditing policies on individual files and folders.

Use the Auditing Entries list box to select the users, groups, or computers whose actions you want to audit. To remove an account, select the account in the Auditing Entries list box, and then click Remove.
 
To add specific accounts, click Add, and then use the Select Users, Contacts, Computers, Or Groups dialog box to select an account name to add. When you click OK, you'll see the Auditing Entry For New Folder dialog box If you want to audit actions for all users, use the special group Everyone. Otherwise, select the specific user groups or users, or both, that you want to audit.
 
Select the Successful or Failed check boxes, or both, for each of the events you want to audit. Successful logs successful events, such as successful file deletes. Failed logs failed events, such as failed file deletions. The events you can audit are the same as the special permissions listed
 
Choose OK when you're finished. Repeat this process to audit other users, groups, or computers.

The selected events will then be written to the Security Log.