This is something I've been trying to do for a while. The best solution I've come up with is an audit table.
I've looked at writing apps that don't actually delete records, rather they flag them as deleted so that the audit simply needs to store PK, user details, date/time and action but it becomes more hassle that it's worth.
Another option was to write the deleted record to an audit db, but again it became too much aggro.