How should I build custom history tracking for a large number of fields?

Here is my solution. It works dynamically on all fields of certain types (I have tested with String, Picklist, Date, DateTime, Integer, Boolean). You could extend it so that not only updates, but also inserts are tracked. Edit: For some weeks, this code has been working in production without problems.

Be aware that it can compromise security because changes to fields are tracked even if the user cannot see the field on the page layout.

The object for which the history information will be kept is called Compliance__c; the history is stored in ComplianceHistory__c.

This is inside the after update trigger for Compliance__c:

    //get all fields from compliance that we want to check for changes
    Map<String, Schema.SObjectField> allComplFieldsMap = Schema.SObjectType.Compliance__c.fields.getMap();
    complFieldsToTrack = new Map<String, Schema.DescribeFieldResult>();
    for (Schema.SObjectField complField : allComplFieldsMap.values()) {
        Schema.DescribeFieldResult describeResult = complField.getDescribe();
        //choose which fields to track depending on the field type
        if (describeResult.getType() == Schema.DisplayType.Boolean ||
            describeResult.getType() == Schema.DisplayType.Combobox ||
            describeResult.getType() == Schema.DisplayType.Currency ||
            describeResult.getType() == Schema.DisplayType.Date ||
            describeResult.getType() == Schema.DisplayType.DateTime ||
            describeResult.getType() == Schema.DisplayType.Double ||
            describeResult.getType() == Schema.DisplayType.Email ||
            describeResult.getType() == Schema.DisplayType.Integer ||
            describeResult.getType() == Schema.DisplayType.MultiPicklist ||
            describeResult.getType() == Schema.DisplayType.Percent ||
            describeResult.getType() == Schema.DisplayType.Phone ||
            describeResult.getType() == Schema.DisplayType.Picklist ||
            describeResult.getType() == Schema.DisplayType.String ||
            describeResult.getType() == Schema.DisplayType.TextArea ||
            describeResult.getType() == Schema.DisplayType.Time ||
            describeResult.getType() == Schema.DisplayType.URL) 
        {
            //don't add standard fields that are not necessary
            if (describeResult.getName() != 'CreatedDate' &&
                describeResult.getName() != 'LastModifiedDate' &&
                describeResult.getName() != 'SystemModstamp' &&
                //only add fields that are visible to the current user
                describeResult.isAccessible() &&
                //do not add formula fields
                !describeResult.isCalculated()
                )
            {
                complFieldsToTrack.put(describeResult.getName(), describeResult);
            }
        }
    }

The following is done for every object in Trigger.new inside a loop:

    Compliance__c oldCompl = (Compliance__c)oldSo;
    Compliance__c newCompl = (Compliance__c)so;

    for (Schema.DescribeFieldResult fieldDescribe : complFieldsToTrack.values()) {
        if (oldCompl.get(fieldDescribe.getName()) != newCompl.get(fieldDescribe.getName())) {
            ComplianceHistory__c complHistory = createUpdateHistory(fieldDescribe, oldCompl, newCompl);
            historiesToInsert.add(complHistory);
        }
    }

Here is the method to populate the history object referenced in the loop:

private ComplianceHistory__c createUpdateHistory(Schema.DescribeFieldResult field, Compliance__c oldCompl, Compliance__c newCompl) {
    ComplianceHistory__c complHistory = new ComplianceHistory__c();
    complHistory.Compliance__c = newCompl.Id;
    complHistory.Event__c = 'Edit';
    complHistory.Field__c = field.getLabel();
    complHistory.User__c = UserInfo.getUserId();
    // shorten strings that are longer than 255 characters (can happen if the field has the type textArea)
    if (complHistory.OldValue__c != null) complHistory.OldValue__c = complHistory.OldValue__c.abbreviate(255);
    if (complHistory.NewValue__c != null) complHistory.NewValue__c = complHistory.NewValue__c.abbreviate(255);
    complHistory.EditDate__c = System.now();
    return complHistory;
}

In the end, the history records are inserted:

    if (!historiesToInsert.isEmpty()) {
        //remove duplicate history entries
        List<ComplianceHistory__c> historiesToInsertWithoutDuplicates = new List<ComplianceHistory__c>();
        Set<ComplianceHistory__c> historiesSet = new Set<ComplianceHistory__c>();
        historiesSet.addAll(historiesToInsert);
        historiesToInsertWithoutDuplicates.addAll(historiesSet);

        //insert the rest
        insert historiesToInsertWithoutDuplicates;
    }

This is a common task in database design in general. There are two approaches, depending on your needs. It sounds like you probably just need the first option.

1. If you just need to record the value changes, then a table with Old Value, New Value, Modified By, Modified Date, and a primary key is the simplest way to go. The values stored can just be their string (or serialized equivalent) version, as suggested by Lex.

2. If you need a complete picture of the record at a point in time then a full history object may be needed. In this case you would have a full shadow object that gets populated whenever something is changed.

Fr more ideas and best practices I would suggest searching for "SQL history table best practices".