Given an Eisenstein series $E_k$ (of level 1), it is a polynomial $P_k(E_4,E_6)$ in $E_4$ and $E_6$, and http://en.wikipedia.org/wiki/Eisenstein_series#Recurrence_relation should give a finite algorithm for doing so.
Do we know any properties of these polynomials $P_k$ or are there any formulas? A quick internet search didn't turn up with anything, but maybe I just didn't know what to search.
(As before, if somebody knows enough about the subject to tell me if this is appropriate for overflow, e.g. not found in a common textbook, then I might want to post it there instead.)
I'm not quite sure what you are looking for. But yes, there are some results about the polynomials $P_k$. For instance, Swinnerton-Dyer has proven that if $p>5$ is a prime, then $P_{p-1}$ is $p$-integral, and its reduction mod $p$ has no multiple factors (so, a fortiori, $P_{p-1}$ also has no multiple factors). Also, $P_{p-1}-1$ is irreducible.