The genus spectrum of a finite group G is the set of all g such that G acts faithfully on a compact Riemann surface of genus g. It is an open problem to find a general description of the genus spectrum of the groups in interesting classes, such as the Abelian p-groups. Motivated by earlier work of Talu for odd primes, we develop a general combinatorial method, for arbitrary primes, to obtain a structured description of the so-called reduced genus spectrum of Abelian p-groups, including the reduced minimum genus. In particular, we determine the complete genus spectrum for a large subclass, namely, those having ‘large’ defining invariants. With our method we construct infinitely many counterexamples to a conjecture of Talu, which states that an Abelian p-group is recoverable from its genus spectrum. Finally, we give a series of examples of our method, in the course of which we prove, for example, that almost all elementary Abelian p-groups are uniquely determined by their minimum genus, and that almost all Abelian p-groups of exponent p2 are uniquely determined by their minimum genus and Kulkarni invariant.