Do you mean the record is deleted by a user on the form (front-end) or do you mean if the record is deleted by a user who has direct access to the underlying table?
The Form object (front-end) has many events that could be used to call your e-mail notificaiton.
Table Object
In
Access 2010 there is a feature. Take a table and put it into Design Mode.
On the tool bar choose Table Tools
Choose the option Create Data Macro - in the pull down - choose After Delete
From there you can for example Add New Action - one of them is Send Email
For a general video tutorial, scroll down to Data Macros at:
http://office.microsoft.com/en-us/access-help/what-s-new-in-microsoft-access-HA010342117.aspx
It doesn't answer your specific question, but my instruction along with this video should help.