We investigate the combinatorial properties of the traces of the nth Hecke operators on the spaces of weight 2k cusp forms of level N. We establish examples in which these traces are expressed in terms of classical objects in enumerative combinatorics (e.g., tilings and Motzkin paths). We establish in general that Hecke traces are explicit rational linear combinations of values of Gegenbauer (also known as ultraspherical) polynomials. These results arise from "packaging" the Hecke traces into power series in weight aspect. These generating functions are easily computed by using the Eichler-Selberg trace formula.