One way of thinking about the construction of companion matrices is the following. Suppose $P(x)$ is a monic polynomial and we'd like to construct a matrix with $P(x)$ as characteristic polynomial. We do this by writing down the algebra
$$A = F[x]/P(x)$$
where $F$ is the underlying field. By construction, the operator
$$L_x : A \ni a \mapsto xa \in A$$
given by multiplication on the left by $x$ has minimal polynomial $P(x)$; it's not hard to show that in fact it has characteristic polynomial $P(x)$. So any matrix describing $L_x$ will have the right characteristic polynomial. To write down such a matrix we write down a basis for $A$, and a very convenient basis is $\{ 1, x, \dots, \dots x^{n-1} \}$ where $n = \deg P$. It's an exercise from here to show that you get exactly the companion matrix.
The analogous construction for finite groups, which overlaps with the above construction for cyclic groups and only for cyclic groups, is to start with a finite group $G$ and construct the group algebra
$$A = F[G].$$
Then the operators $L_g$ given by multiplication by $g \in G$ have matrix representations given by using the basis given by the elements of $G$. These matrices are always permutation matrices. This construction produces what is called the regular representation of $G$.