Euler density is simply the integrand in $2n$ dimensions of the integral that is equal to the Euler characteristic. The Euler characteristic may be written as the integral of the following Euler density in $2n$ dimensions: $$E_{2n} = \frac{1}{2^n} R_{i_1 j_1 k_1 l_1} \dots R_{i_n j_n k_n l_n} \epsilon^{i_1 j_1 \dots i_n j_n} \epsilon^{k_1 l_1 \dots k_n l_n} $$ Note that for $n=1$ i.e. in two dimensions, it is linear in the Riemann tensor - and therefore also in the Ricci scalar (because the Riemann tensor is fully determined by the Ricci scalar in 2D). In four dimensions, the Euler density is quadratic in the Riemann tensor, and so on.
The Euler character - a "regularized number of points in a manifold" - may also be calculated in many other ways, e.g. for polytopes by adding the number of faces, subtracting edges, adding vertices, etc. For nice manifolds, it's only nonzero for even-dimensional manifolds. For closed orientable two-dimensional Riemann surfaces, it is given by $2-2h$ where $h$ is the number of handles (the genus also known as $g$). One may construct a general open/closed orientable/unorientable two-dimensional manifold by adding $b$ (circular) boundaries i.e. holes and $c$ crosscaps (holes with identified antipodal points, creating an unorientable manifold) and the total Euler characteristic is then $$ \chi = 2-2g - b - c.$$ You should imagine that if there is a function $L(\sigma^i)$ depending on the manifold's coordinates sigma such that $L$ has units of $U$, the path integral $\int DL(\sigma^i)$ has units of $U^\chi$ where $\chi$ is the Euler characteristic: that's what I meant by saying that $\chi$ is the regularized number of points.
So the Euler characteristic (or character) is arguably the most important and most elementary topological invariant of a manifold. The fact that the integral of $E_{2n}$ is a topological invariant may be seen by calculating its variation which vanishes (for any variation of the metric) - one reduces the derivative to some of the standard identities for the Riemann tensor, especially the two Bianchi identities involving antisymmetrization (and, in one case, one derivative).
The derivation of the trace of the stress-energy tensor is done for $d=2$ in Polchinski's "String Theory", Volume I. Equation (3.4.31) says $$T^a_a (\sigma) = -\frac{C}{12} R(\sigma)$$ where $R$ is the Ricci scalar, also interpretable as a multiple of the Euler density. The $C$ ends up being a definition of the central charge. I don't know the general form of a similar equation in $d$ dimensions but its exact form - at least the parameters - do depend on the theory. I guess that in general, the trace is equal to some linear combination of the Euler density and perhaps some other generators besides the stress-energy tensor.