This is really just a long comment. I feel that the honor (naturality) of the trace has been called into question, and so it must be defended ;) I'm certain there are many other elegant things that can be said...but here are my two cents:
First of all, one nice thing about a trace is that it is not coordinate dependent. This is because $Tr(S^{-1}TS)=Tr(SS^{-1}T)=Tr(T)$ for all $T$ in whatever algebra you are considering on which $Tr$ lives.
As for the general significance of the trace, you may want to have a look at the Riesz representation theorem for bounded linear functionals on the algebra of continuous functions with compact support with respect to pointwise multiplication. This theorem facilitates viewing a trace (or continuous functionals in general) as an integral in certain important abelian algebras.
If you are looking at physics from a point of view that incorporates $C^{\ast}$-algebras, then traces play an important role. Say, for example, you are thinking about quantum mechanics from the operator algebra point of view. A good sort of $C^{\ast}$ -algebra in which to do this is a von Neumann algebra, since these are generated by self-adjoint projections...which amount to 'yes' or 'no' questions (a nice description I first saw posted on John Baez's blog). A trace on the von Neumann algebra readily expresses a notion of dimension that generalizes the usual Hilbert space dimension. In (finite) matrices, two projections have ranges with the same dimension if and only if these projections have the same trace. So, equivalence classes of projections are given by the possible traces: $\{0,1,2,...,dim(H)\}$. There are von Neumann algebras that exhibit continous dimension (the equivalence classes range over $[0,1]$). All such algebras admit a (normal) trace state...which witnesses the dimension. In short, traces seem to be no more artificial than dimension...largely because of the coordinate independence.
Also, traces are important in noncommutative geometry. For example, a non-normal trace called the Dixmier trace plays the role of the integral in the noncommutative differential calculus. For more on this, see Connes's book.