Wikipedia describes Kendall and Smith's 1938 statistical randomness tests like this:
The frequency test, was very basic: checking to make sure that there were roughly the same number of 0s, 1s, 2s, 3s, etc.
The serial test, did the same thing but for sequences of two digits at a time (00, 01, 02, etc.), comparing their observed frequencies with their hypothetical predictions were they equally distributed.
The poker test, tested for certain sequences of five numbers at a time (aaaaa, aaaab, aaabb, etc.) based on hands in the game poker.
The gap test, looked at the distances between zeroes (00 would be a distance of 0, 030 would be a distance of 1, 02250 would be a distance of 3, etc.).
It is not obvious to me that these four particular tests were chosen with any deep understanding of how best to detect nonrandomness. Rather, it seems each one was probably chosen for simplicity.
Well, it's easy to see why early work in the field would be like that. But fast forward to 1995 and George Marsaglia's Diehard tests seem, on the surface, just as ad hoc:
Birthday spacings: Choose random points on a large interval. The spacings between the points should be asymptotically Poisson distributed. The name is based on the birthday paradox.
Overlapping permutations: Analyze sequences of five consecutive random numbers. The 120 possible orderings should occur with statistically equal probability.
(...and so on)
It is not obvious to me that these tests are really independent (i.e. that none is entirely redundant, rejecting only sequences also rejected by at least one of the other tests), or that there aren't obviously better generalizations of them, much less that they were chosen as a set to try to cover any particular space efficiently.
Ideally, a test suite would be designed to reject as many sequences of low Kolmogorov complexity as possible with minimal computation and false alarms. Is a more theoretical approach to this possible? Why hasn't it happened? —Or is there more to the state of the art than meets the eye?