For the most part by bitslicing. Some implementations calculate the S-box explicitly using the algebraic relationships in the finite field but doing so is awfully slow.
I should add here that I met an incredibly intelligent young man named Julian from Dartmouth and doing some work with MIT who is proving with COQ and a model of a CPU that his implementation of cache lookups for (various) crypto algorithms results in exactly the same line patterns and the number of cpu ticks is similarly invariant. Some people go the extra mile.