Prefs -> File Operations -> Deleting Files has all the options.
(When deleting to the Recycle Bin, the Windows Recycle Bin settings can also have an effect but I don't think the Recycle Bin will be used when deleting files from a NAS device.)
If you have certain versions of Windows at the other end then you can use Shadow Copy / VSS (like "Previous Versions" in Pro/Ultimate/etc. versions of Vista and Windows 7), which is similar.
I don't know what brand NAS you have but the one I have (QNAP) has what it calls a "Network Recycle Bin" share folder. All files deleted from the NAS go to the NRB.
Though I have this feature disabled, it's very nice to have it there as an option.