The main data structure for polynomials is a linked list of terms (coefficient and monomial), sorted in decreasing order with respect to the monomial order, and with 0 elements not represented. There are variants on this, but for computing Groebner bases this is (or, appears to be the) the most useful version. Sometimes polynomials are stored as 2 vectors: an array of coefficient elements, and an array of monomials. This often has better cache behavior, and I plan on changing all uses of linked lists inside Groebner bases and resolutions to this structure (Some have been changed already: including for the "minimalBetti" free resolutions, for noncommutative polynomials, and in the mathicgb Groebner implementations).
For operations not involving Groebner bases, the hash table representation is often pretty good, and is used for example at top level in computations in the package NCAlgebras. There are also heap based structures, which are are used during multiplication of polynomials. These are not so good for Groebner computations, it appears, as one really wants an operation to find the lead monomial.
In Macaulay2, except for univariate polynomials (and even mostly for univariate polynomials), all polynomials are considered as sparse sums of monomials. Truly huge exponents are not allowed though, currently.
Does this answer any of your questions?