A left regular representation of a finite group $G$ is given by sending each $g \in G$ to the permutation matrix of $\sigma$, where $\sigma$ is the permutation induced on the elements of $G$ by left multiplication by $g$. In other words, we label the elements of $G$ as $g_1,\ldots,g_n$, where $n = \vert G \vert$. Then given $g \in G$, we let $\sigma_g \in S_n$ such that
$$gg_i = g_{\sigma_g(i)}$$
for each $i = 1,\ldots,n$. Then a left regular representation for $G$ is given by sending $g$ to the permutation matrix $M_{\sigma_g}$ of $\sigma_g$, i.e., the matrix whose $i$th column has $1$ in position $\sigma_g(i)$ and $0$ elsewhere. If $g = e$, then of course $M_{\sigma_g}$ is the identity matrix, which has trace equal to $n$. On the other hand, if $g \neq e$, then $gg_i \neq g_i$ for all $i = 1\ldots,n$. Therefore the diagonal entries of $M_{\sigma_g}$ are all $0$, hence $M_{\sigma_g}$ has trace $0$.
The right regular representation is the same except you multiply by $g$ on the right instead of on the left.