I already audit authorization success, failure and logout.
I've considered auditing (logging) every method call and keeping a version of every row and column that was ever modified, but both of those options will greatly increase the complexity of auditing. Auditing a random subset sees too random.
The legal specs (FISMA, C&A) just say something needs to be audited.
Are there any other non-domain specific auditing strategies I'm forgetting?
Considering that auditing is often about accountability you may wish to log those actions that could contribute to any event where someone/something needs to be accountable..
It is a good idea to keep some of these things versioned, such that you can roll-back changes to vital data. Adding 'who altered' in the first place is quite straight forward.
Unless someone has direct access to the database, often application logging of any event that affects the database ... such as a transaction altering many tables ... may be sufficient. So long as you can link auditable logical action to a logical unit of accountability, regardless of what subsystem it affects, you should be able to trace accountability.
You should not be logging method calls and database alterations directly, but the business logic that led to those calls and changes, and who used that logic. Some small amount of backend code linking causality between calls/table alterations and some audit-message would be beneficial too (if you have resources).
Think of your application's audit-elements as a tree of events. The root is what you log, for example 'Dave deleted customer record 2938'. Any children of the root can be logged and you can tie it to the root, if it is important to log it as part of the audit event. For example you can assert that some audit event, 'Dave deleted ...' was tied to some billing information also going walkies as part of a constraint or something
But I am not an expert.
I agree with a lot of what Aiden said, but I strongly believe that auditing should be at the database level. Too many databases are accessed with dynamic sql so permissions are at the table level (at least in SQL Server). So the person committing fraud can enter delete or change data at the database bypassing all rules. In a well-designed system only a couple of people (the dba and backup) would have the rights to change audit triggers in prod and thus most people could get caught if they were changing data they were not authorized to change. Auditing through the app would never catch these people. Of course there is almost no way to prevent the dbas from committing fraud if they choose to do so, but someone must have admin rights to the database, so you must be extra careful in choosing such people.
We audit all changes to data, all inserts and all deletes on most tables in our database. This allows for easy backing out of a change as well as providing an audit trail. Depending on what your database stores, you may not need to do that. But I would audit every financial transaction, every personnel transaction, and every transaction having to do with orders, warehousing or anything else that might be subject to criminal activity.
If you really want to know what absolutely must be audited, talk to the people who will be auditing you and ask what they will want to see.