The easiest way is to explicitly express the change of basis as
[tex]A \to A' = B A B^{-1}[/tex]
and use the cyclic property
[tex]\operatorname{Tr}(ABC) = \operatorname{Tr}(BCA) = \operatorname{Tr}(CAB)[/tex]
Or you can use that
[tex]\operatorname{Tr}(A) = \sum \lambda[/tex]
where [itex]\lambda[/itex] are the eigenvalues, and show that these are basis invariant
(for example, show that if v is a corresponding eigenvector, that [itex](B A B^{-1}) (B v B^{-1}) = \lambda v[/itex] as well).
Actually, upon reading back my answer, I noted a little error. Instead of
[tex]
(B A B^{-1}) (B v B^{-1}) = \lambda v
[/tex]
I should of course have said
[tex]
(B A B^{-1}) (B v B^{-1}) = \lambda (B v B^{-1})
[/tex]
which simply says that if [itex]A v = \lambda v[/tex] then [itex]A' v' = \lambda v'[/itex] where the primes refer to matrices and vectors in the new basis (i.e. [itex]A' = B A B^{-1}[/itex] and [itex]v' = B v B^{-1}[/itex]).