I have been wanting to enable the Active Directory Recycle Bin for some time following our upgrade to Windows Server 2008 R2. After some research, I found “The AD Recycle Bin: Understanding, Implementing, Best Practices, and Troubleshooting” article in the TechNet Blogs that explained the whole process.
In short, your domain and forest functional levels must be on Windows Server 2008 R2 first.
Then it is as easy as the following two Powershell commands on a domain controller as a Domain Admin:
Enable-ADOptionalFeature 'Recycle Bin Feature' -Scope ForestOrConfigurationSet -Target forestrootdomainname