There are basically 3 senses of "Hecke algebra", and they are related to each other. The modular-form sense is a special case of all three.
The oldest version is that motivated by modular forms, if we think of modular forms as functions on (homothety classes of) lattices: the operator $T_p$ takes the average of a $\mathbb C$-valued function over lattices of index $p$ inside a given lattice. Viewing a point $z$ in the upper half-plane as giving the lattice $\mathbb Z z + \mathbb Z$ makes the connection to modular forms of a complex variable.
One important generalization of this idea is through repn theory, realizing that when modular forms are recast as functions on adele groups, the p-adic group $GL_2(\mathbb Q_p)$ acts on modular forms $f$. To say that $p$ does not divide the level becomes the assertion that $f$ is invariant under the (maximal) compact subgroup $GL_2(\mathbb Z_p)$ of $GL_2(\mathbb Q_p)$. Some "conversion" computations show that $T_p$ and its powers become integral operators (often mis-named "convolution operators"... despite several technical reasons not to call them this) of the form $f(g) \rightarrow \int_{GL_2(\mathbb Q_p)} \eta(h)\,f(gh)\,dh$, where $\eta$ is a left-and-right $GL_2(\mathbb Z_p)$-invariant compactly-supported function on $GL_2(\mathbb Q_p)$. The convolution algebra (yes!) of such functions $\eta$ is the (spherical) Hecke algebra on $GL_2(\mathbb Q_p)$.
A slightly larger, non-commutative convolution algebra of functions on $GL_2(\mathbb Q_p)$ consists of those left-and-right invariant by the Iwahori subgroup of matrices $\pmatrix{a & b \cr pc & d}$ in $GL_2(\mathbb Z_p)$, that is, where the lower left entry is divisible by $p$. This algebra of operators still has clear structure, with structure constants depending on the residue field cardinality, here just $p$. (The Iwahori subgroup corresponds to "level" divisible by $p$, but not by $p^2$.) This is the Hecke algebra attached to the affine Coxeter group $\hat{A}_1$.
Replacing $p$ by $q$, and letting it be a "variable" or "indeterminate" gives an example of another generalization of "Hecke algebra".
The latter situation also connects to "quantum" stuff, but I'm not competent to discuss that.
Edit: by now, there are several references for the relation between "classical Hecke operators" (on modular forms) and the group-theoretic, or representation-theoretic, version. Gelbart's 1974 book may have been the first generally-accessible source, though Gelfand-PiatetskiShapiro's 1964 book on automorphic forms certainly contains some form of this. Since that time, Dan Bump's book on automorphic forms certainly contains a discussion of the two notions, and transition between the two. My old book on Hilbert modular forms contains such a comparison, also, but the book is out of print and was created in a time prior to reasonable electronic files, unfortunately.
This is a layman answer. Hecke operators commute and are self-adjoint, hence the modular forms which are eigenvectors wrt. all Hecke operators form a basis of the space of all modular forms (and the same for cusp forms). If $f$ is such an eigenvector then the L-series corresponding to $f$ has multiplicative coefficients, i.e. it can be represented by an Euler product (over all primes). So AFAIK, Hecke operators are important for connections of modular forms with number theory.
Best Answer
If $M$ divides $N$, and $d$ divides $N/M$, then for any modular form $f(\tau)$ on $\Gamma_0(M)$, the function $f(d\tau)$ is a modular form on $\Gamma_0(N)$.
Let's write $V_N$ for the vector space of cuspforms on $\Gamma_0(N)$ (of some fixed weight). Then the above map, i.e. $f(\tau) \mapsto f(d\tau)$, gives an embedding of $V_M$ into $V_N$; write $V_{M,d}$ its image.
Then the space of old forms in $V$ is the subspace of $V$ obtained by taking the sum over all proper divisors $M$ of $N$ and all possible corresponding choices of $d$ of the subspaces $V_{M,d}$. We use the word old for them because these forms, while they have level $N$, actually come from a smaller level (namely $M$), and so are "old" from the point of view of the level $N$. The space of new forms is the orthogonal complement in $V$ of the space of old forms; elements of $V$ are genuinely new to level $N$, hence their name.