In Lee's book, the following reasoning is used to prove the existence of a Tubular neighborhood:
Suppose that $M$ is an embedded submanifold of $\mathbb R^n$. Then we can define $NM : = \{(x,v)|v \bot T_xM\}$ where orthogonality is defined using the Euclidean metric. To do that we need to identify $T_xM$ with $\mathbb R^n$. Then there is a choice to make.
How is the whole thing independent of this choice?
As Mosher points out in the comments, asking whether a tubular neighbourhood defined this way is independent of the choice of Riemannian metric doesn't make sense because tubular neighbourhoods are not unique.
Let's suppose you are really asking the following:
One answer is provided by the notion of manifold pairs.
We can consider "germs" of submanifolds by looking at a certain equivalence relation of manifold pairs:
Now fix your submanifold $N$ embedded in some larger manifold $W$ and let $M_1$ and $M_2$ be tubular neighbourhoods of $N$ in $W$. Then $M = M_1\cap M_2$ is also a tubular neighbourhood of $N$ in $W$ and we see that the pair $(N,M)$ demonstrates that $(N,M_1)$ and $(N,M_2)$ are equivalent.
Since any two tubular neighbourhoods of $N$ in $W$ are equivalent as manifold pairs we may conclude that
I learned about this definition of manifold pairs and their equivalence by reading "symplectic manifolds and their lagrangian submanifolds" by Alan Weinstein.