H.264's complexity increase mainly comes from the large number of prediction modes and macroblock types, which are essentially attempts to encode more efficiently the differences between successive frames.
The maths has actually gotten simpler; the predecessors are all traditional DCT-based (JPEG-like) codecs while H.264 uses a simple integer approximation. Regardless, from a decoder implementation perspective, the theory behind it all is not that important; the spec tells you exactly what you need to do, and the increase in complexity is mainly reflected in needing to write more code to handle the larger number of cases.
H.261 is simple because it has a choice of only two resolutions, one framerate, two frame types (I and P), and 10 macroblock types.
H.262/MPEG-2 is already a significant increase in complexity since it supports a varying set of resolutions, framerates, interlacing, and chroma subsampling, has 3 frame types (I, P, B), 20 macroblock types (dependent on frame type), and more complex motion compensation.
H.263 has no interlacing but adds optional intra prediction, more advanced motion vector encoding, and a few other features.
H.264 has about 50 macroblock types, even more complex intra prediction, and motion compensation has a larger choice of which frames to predict from.