There are a lot of interesting answers here and in similar questions. The only things that I can add from personal experience are:
Put your audit table in another database. Ideally, you want separation from the original data. If you need to restore your database, you don't really want to restore the audit trail.
Denormalize as much as reasonably possible. You want the table to have as few dependencies as possible to the original data. The audit table should be simple and lightning fast to retrieve data from. No fancy joins or lookups across other tables to get to the data.