Does a positive semidefinite matrix always have a non-negative trace?

Suppose that $A = [a_{ij}]_{i,j=1}^n$ is such that $a_{ii} < 0$ for some $i$. Let $e_i$ be the $i$th standard basis vector; that is, $$ e_i = (\overbrace{0,\cdots,0}^{i-1},1,0,\dots,0) $$ then $e_i^T Ae_i = a_{ii} < 0$, which means that $A$ is not positive semidefinite.

So, if $A$ is positive semidefinite, then all diagonal elements are non-negative, which means that the trace is non-negative.

Yes. If the matrix is semi-positive definite, all the eigenvalues are non-negative. The trace being equal to the sum of eigenvalues, we conclude that the trace has to be non-negative.

We know that positive semi-definite matrices have nonnegative eigenvalues, and the trace of a matrix is equal to the sum of its eigenvalues. Because sum of nonnegative numbers is nonnegative, the trace of a positive semi-definite matrix is nonnegative.