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).