I might not be seeing the wood for all the trees in what follows.
If $f(z)=\sum_{n}a_{n}z^{-n}$ is a Hecke eigenform, the coefficients $a_{n}$ satisfy the relation $$a_{p^{j}}=a_{p^{j-1}}a_{p}-pa_{p^{j-2}}$$ if $p$ is a prime and $$a_{mn}=a_{m}a_{n}$$ if $m$ and $n$ are coprime.
So far, so good. How does this relation imply the summation formula $$\sum_{j}a_{p^{j}}p^{-js}=\frac{1}{1-a_{p}p^{-s}+p^{1-2s}}\text{?}$$
OK, I got it now. Set $x=p^{-j}$ and expand the fraction into a Taylor series; the recurrence relation for the coefficients follows easily. I should have figured that one out myself.