The best way to do a history of changes IMO is a seperate table that identifies all changes, inserts, updates, and deletes, and stores old and new data. It depends on how granular you need it, is primary key, a list of columns changed, the old and new values, enough ?

As for deletes, the other possibility is always to use a deleted flag, so no data is deleted, then it's essentially an update. That's a pretty wide change on an existing DB, though.