Let $F_n = \langle u_1,...,u_n \rangle$ be the free group on $n$ generators. I found this post on showing that the conjugacy class of an non-identity element is infinite.
One suggestion is to show that $C_{F_n}(g)$ is an infinite cyclic group; but that doesn't seem helpful. The other suggestion is to use the fact that "elements of the free group are presented by free words without relations other than $a^{−1}a=1$ and $aa^{−1}=1$."; but that doesn't seem very rigorous. I am reading the wikipedia page on free groups and it doesn't seem to define them as groups without relations other than those relations which follow from group theory axioms. The definition is a little more complicated, albeit more precise, than that.
How does one rigorously prove that $F_n$ has the ICC property? One thing I tried was to exhibit an infinite collection of distinct cosets of $C_{F_n}(g)$, but my methods were not rigorous (e.g., my proofs were relying on the ostensibly imprecise fact that $F_n$ contains no relations other than those that follow from the group axioms).
A free group $F_S$ over a set $S$ is ICC unless $S$ has cardinal 1.
Clearly it's enough to do it for $S$ finite.
To prove that a group is ICC it's enough to embed it as a dense subgroup into a connected (or just with no proper open subgroup of finite index) Hausdorff topological group with trivial center. Indeed $F_S$ for $2\le |S|$ can be embedded in this way, for instance into $\mathrm{PSL}_2(\mathbf{R})$.
Of course whether this approach is helpful depends on your background.