The argument of orangeskid can be generalized to all cases where the base field is infinite. Unfortunately, for the general case my impression is that no such basic proof is known.
Typically, the statement is given as a corollary of the rational canonical form, which is a normal form for square matrices under the equivalence notion of similarity. In contrast to the Jordan normal form, the rational canonical form works over any field, no matter if algebraically closed or not. The rational canonical form results as an application of the classification of finitely generated modules over principal ideal rings, which should be found in most book on abstract algebra.
The argument is the following:
If $L$ is a field and $A,B$ are square matrices with entries in $L$, then $A$ and $B$ are similar if and only if they have the same rational canonical form. The rational canonical form is determined by the invariant factors of the matrices, which are polynomials over $L$.
If the entries of $A$ are contained in a subfield of $K$, then the coefficients of the invariant factors are contained in $K$, too.
This shows that in this case, $A$ and $B$ are similar over $L$ if and only if they are similar over $K$.
Another way to see it: The rational canonical form has the nice property of being invariant under the transition to extension fields. Actually, this is the meaning of the word "rational" in this context.