Suppose, toward a contradiction, that by counting the same finite set $S$ twice, you get two different results, say the two natural numbers $m<n$. So your counting has produced two bijections, one between $S$ and $\{1,2,\dots,m\}$ and one between $S$ and $\{1,2,\dots,n\}$. Composing the one bijection with the inverse of the other, you get a bijection from the set $\{1,2,\dots,n\}$ to a proper subset $\{1,2,\dots,m\}$. The crux of the proof is then to show, by induction on $n$, that there is no one-to-one map of $\{1,2,\dots,n\}$ into any proper subset of itself.
The basis of the induction, $n=0$, is trivial, as the empty set has no proper subset. For the induction step, assume the result for $n$ and suppose $f$ were a counterexample for $n+1$. Modifying $f$ slightly (changing just one or at most two values), you can arrange that $f(n+1)=n+1$. Then, being one-to-one, $f$ has to map $\{1,2,\dots,n\}$ into itself and therefore onto itself (by induction hypothesis). But then $f$ maps $\{1,2,\dots,n+1\}$ onto itself as well.
I've assumed here that a reasonable notion of natural number is available; that seems to be implicit in your reference to counting. It might, however, be useful to observe that the "meat" of the argument works even without natural numbers. Specifically, one can define finiteness by saying that a set $S$ is finite iff, whenever $X$ is a family of subsets of $S$ containing $\varnothing$ and $x\cup\{s\}\in X$ for all $x\in X$ and $s\in S$, then $S\in X$. (In other words, $S$ can be obtained from $\varnothing$ by repeatedly adjoining single elements.) With this definition, one can show, by essentially the same argument as above, that there is no one-to-one map from a finite set into a proper subset of itself.
