Note that to evaluate a line integral, you must parameterize the curve on which you are evaluating the line integral with some parameter $t$. A common curve that we are interested in integrating along, for example, is the unit circle, which we know well can be parameterized as
$$(\cos t, \sin t), ~ 0 \leq t \leq 2\pi$$
But note that this parameterization is not unique! Note that
$$(\cos t^2, \sin t^2), 0 \leq t \leq \sqrt{2\pi}$$
is also a parameterization of the unit circle (and there are infinitely more such parameterizations of the unit circle). So when we say that line integrals are independent of choice of parameterization, it means that the line integral should evaluate to the same result independent of which such parameterization of the curve we choose. So if my line integral was along the unit circle, I could choose either of the above parameterizations and I should get the same result.
We will need the following definition: a regular parameterization $p(t) : [\alpha, \beta] \to C$ of a curve $C$ is one of nonzero velocity, i.e. $p'(t) \neq \vec{0}$ for every $t \in [\alpha, \beta]$.
We will now prove this result. Let us assume the curve is smooth, and we have two regular parameterizations, $p(t): [\alpha, \beta] \to C$ and $q(u): [\gamma, \delta] \to C$, where $C$ is the curve you are trying to integrate along. Assume furthermore that there is also a smooth function $r(t): [\alpha, \beta] \to [\gamma, \delta]$ such that $q(r(t)) = p(t)$. (For essentially all parameterizations, you can find such a function.) We want to show that
$$\int_\alpha^\beta \mathbf{F}(p(t)) \cdot p'(t) dt = \int_\gamma^\delta \mathbf{F}(q(u)) \cdot q'(u) du$$
Let us apply a change of variables in the integral on the right-hand side. We will replace $u$ by $r(t)$:
$$\int_\gamma^\delta \mathbf{F}(q(u)) \cdot q'(u) du ~ \stackrel{u \to r(t)}{\to} ~ \int_{r(\gamma)}^{r(\delta)} \mathbf{F}(q(r)) \cdot q'(r) r'(t) dt$$
Because $u = r(t) \implies du = r'(t) dt$. Note also that the bounds have changed, as is the case when you change variables. But by the chain rule, we know that
$$p'(t) = \frac d {dt} q(r(t)) = q'(r(t)) \cdot r'(t)$$
With this fact and also the fact that $r(\gamma) = \alpha$ and $r(\delta) = \beta$, we can rewrite the above expression as
$$\int_{\alpha}^{\beta} \mathbf{F}(q(r(t))) \cdot p'(t) dt = \int_{\alpha}^{\beta} \mathbf{F}(p(t)) \cdot p'(t) dt$$
and hence we have achieved our result.
EDIT:
Some questions were asked concerning the existence and properties of the $r(t)$ as described above.
Under what conditions does such an $r(t)$ exist? If the parameterizations $p$ and $q$ (note that the bounds of the parameter are crucial to these parameterizations) trace out the same smooth curve $C$ (in the same directions along the curve), then we can always find such an $r(t)$. To intuitively understand why this is, suppose the two parameterizations $p(t)$ and $q(u)$ have thus far traced out the same part of the curve $C$ and are both at some point $(x,y) = p(t^*) = q(u^*)$. By simply choosing $r(t^*) = u^*$, it can be verified that $p(t^*) = q(r(t^*))$. We can choose the values of $r(t)$ for every such point along the curve in this way, thereby constructing such an $r(t)$. Note that this argument works even for self-intersecting curves, since what matters is the path along the curve that has been traced out thus far.
Don't you need this $r(t)$ to be bijective? Yes, we do, as per the change of variables theorem. But this is actually also always the case when the parameterizations trace out the same curve. Indeed, the function $r$ is monotonically increasing the way we defined it in the answer to the previous question: $r(t_1) > r(t_2) \iff t_1 > t_2$. This is again because the parameterizations trace out the same curve in the same direction. Any monotonically increasing function is invertible, so this assertion holds.
EDIT 2:
What is meant when we say two parameterizations $p$ and $q$ trace the curve in the same directions? This just means that not only is the final curve traced the same, but the two parameterizations follow the same path along the curve. For example, the two following parameterizations of the unit circle:
$$p(t) = (\cos t, -\sin t), ~ q(t) = (\cos u, \sin u), ~ 0 \leq t, u \leq 2 \pi$$
do not trace out the curve in the same directions: one traverses the unit circle counterclockwise, and the other clockwise. But the parameterizations
$$p(t) = (\cos t, \sin t), 0 \leq t \leq 2 \pi; ~ q(u) = (\cos u^2, \sin u^2), 0 \leq u \leq \sqrt{2 \pi}$$
do trace out the curve in the same directions. The only difference, you might say, is that the parameterization $q$ traces out the unit circle "faster" (if you think of $t$ and $u$ as time).
Is $r(t)$ continuously differentiable (smooth)? In fact it is, but this crucially depends on the fact that the parameterizations are regular. It is a result of differential topology (see here) that if $q(r(t))$ is smooth and $q(u)$ is a diffeomorphism (i.e. invertible and differentiable), then $r(t)$ is smooth as well. Since the parameterization $q$ is regular by assumption, we can use the inverse function theorem to conclude that the inverse exists of $q(u)$ exists at every point and is hence well-defined. It would follow from the assumption of $p$'s smoothness that $r(t)$ is smooth. Hence, the change of variables is valid, as $r(t)$ is too a diffeomorphism (the intuitition behind its invertibility was sketched above).
