The phrase "Trace Anomaly" seems to be used in two different ways. What's the relation between the two? I've seen the phrase "Trace Anomaly" refer to two seemingly different concepts, though I assume they must be related in some way I'm not seeing. 
The first way I've seen it used is in the manner, for example, that is relevant for the a-theorem and c-theorem.  That is, given a CFT on a curved background, the trace of the energy-momentum tensor is non-zero due to trace anomalies which relate $T^\mu_\mu$ to different curvatures, that is (in 4D) $T^\mu_\mu\sim b\square R+aE_4+cW^2$, where $E_4$ is the Euler density and $W^2$ is the square of the Weyl tensor.  
The second manner in which I've seen it used is in the context of relating $T^\mu_\mu$ to beta functions as the presence of a non-zero beta function indicates scale dependence, and hence breaks conformal invariance.  For example, Yang-Mills is classically conformally invariant but it is quoted as having a trace anomaly which seems to be of different character than that of the previous paragraph.  As in the Peskin and Schroeder chapter on scale anomalies, it's quoted that since the gauge coupling, $g$, depends on scale due to RG the theory is not quantum mechanically scale invariant (or more generally, I guess, Weyl invariant) and hence $T^\mu_\mu$ is non-zero.  Slightly more precisely, given the YM lagrangian $\mathcal{L}\sim \frac{1}{g^2}{\rm Tr}F^2$, one finds $T^\mu_\mu\sim \beta(g){\rm Tr}F^2$, or something to that effect.  It's my understanding that this second kind of trace anomaly is important for explaining the mass of nuclei, as most of their mass comes from gluonic energy. That might be wrong, though, and it's not so relevant anyway.
What's the relation between these two types of anomalies?  Are they the same thing in disguise?   
 A: A good analogy for the difference between the two can be given in terms of two other examples of anomalies, that are possibly more familiar.
Consider a field theory with a global symmetry, take $U(1)$ for simplicity. At the classical level, the equations of motion lead to the existence of a conserved current (Noether's theorem). 
At the quantum level, the conservation of the current is valid as an operator equation, namely it is valid in correlators at separated points. The two effects, related but very different in nature, that are referred to as anomalies, are:
1) There can exist contact terms in correlators (i.e. terms that are non-zero only when two or more of the operators in the correlator are evaluated at the same point) that do not respect the operator equation. In 4D field theory this typically happens in correlators of three current operators. This is what sometimes is referred to as an 't Hooft anomaly. It does not represent a breaking of the symmetry, because the conservation of the current operator is still valid at separated points, and one still gets a conserved charge. However, it leads to interesting constraints (the coefficients of such contact terms must match between the UV and IR, if the symmetry is not broken along the RG flow).
2) There can be quantum effects (you can think about them as loop corrections, assuming we are in a perturbative setting) that violate the operator equation even at separated points. In this case the symmetry is broken, much like if you add a term in the Lagrangian that does not respect the symmetry. There is no conserved charge any more.
The relation between 1) and 2) can be explained in a slightly refined example. Take the global symmetry to be $U(1)^2$. Than you could have an anomaly of type 1) in a correlator involving one current of the first $U(1)$, and two currents of the second $U(1)$. Now suppose modifying the theory by gauging the second $U(1)$, i.e. coupling the current of the second $U(1)$ to dynamical gauge fields. In the new gauged theory, the first $U(1)$ is broken by an anomaly of type 2). The divergence of its current is now non-zero, and given by the Pontryagin density of the gauge fields of the second $U(1)$.
The first example of trace-anomaly that you discuss is the analogue of 1), while the second is the analogue of 2), when instead of a global $U(1)$ we consider the dilatation symmetry. The first example does not represent a violation of the symmetry, it is just the statement that certain contact terms in the correlators with multiple insertions of the energy-momentum tensor are not compatible with the traceless-ness condition. The second example instead is a genuine violation of the symmetry. The analogy with the $U(1)$ symmetry does not go through when we try to relate 1) with 2), because the equivalent of "coupling the current to gauge field" would be introducing dynamical gravity, which brings us away from the domain of quantum field theory.
This analogy becomes very concrete in supersymmetric theories. There, the energy-momentum tensor belongs to the same multiplet of the current associated to the so-called R-symmetry. Supersymmetry relates the 't Hooft anomaly of this current to the first kind of trace-anomaly that you discuss (i.e. they have the same coefficient). Moreover, when dilatation symmetry is broken by a gauge coupling via the trace anomaly of second type that you discuss, then the current has an anomaly of type 2). Again, the trace anomaly and the current anomaly have the same coefficient by supersymmetry.
A: The two kinds of trace anomalies are related but distinct. The first one that you refer to is the anomaly in Weyl transformations that occurs when you put a CFT on a curved background. The CFT is still exactly conformally invariant in flat space, but this symmetry is broken by the background gravitational field. It's useful to think about CFTs in two dimensions, like the free massless scalar. For these theories, if you rescale the metric by a conformal factor $\exp(2\omega)$, then the partition function is invariant up to a Liouville term, $Z[\exp(2\omega)\delta_{ab}]=Z[\delta_{ab}]\exp(\int R\Box^{-1}R)$, where I've left out factors like 48 and $\pi^2$. You can see this using dimensional regularization, if you'd like to do a computation.
The second kind of trace anomaly that you asked about is referred to as an operatorial anomaly, and occurs even in flat space. It happens when you have a theory that's classically conformally invariant, but not quantumly. You gave the good example of a gauge theory (although the theory of a free Maxwell field actually isn't a CFT outside of 4 dimensions! see http://arxiv.org/pdf/1101.5385.pdf). Another good example is the worldsheet theory for string theory in a curved background, i.e. a nonlinear sigma model.
In general a field theory has both kinds of trace anomalies. If it is a CFT then it doesn't have the operatorial kind.
P.S. you also asked for applications of the operatorial trace anomaly. This is just the beta function of the theory, and from it follows the whole theory of the renormalization group. The most famous application of this in particle physics is probably the use of asymptotic freedom to understand high-energy behavior in QCD at weak coupling.
