Let $F$ be a field and $u\in F$. Further, let $F\subset G$ be a finite extension and $v\in G$ such that $v^n=u$ for $n>0$.
How would I show that there exists a $\tilde{u}\in F$ such that $u^{[G:F]}=(\tilde{u})^n$?
My first thought was to use the norm map $N_{G/F}(x)=\Pi_{\sigma\in X(G/F)}\sigma(x)$, where $X(G/F)$ is the fundamental set for $F\subset G$. However, I wouldn't know how to continue on this path.
Your idea is correct, but let's use another definition of "norm" : let's see $G$ as a finite-dimensional $F$-vector space, and for any $x\in G$ put $L_x:G\to G$ defined by $L_x(a)=xa$, which is a $F$-linear map. Then define $N_{G/F}(x) := \det(L_x)\in F$.
It's easy to see that $N_{G/F}(xy) = N_{G/F}(x)\cdot N_{G/F}(y)$ (because $L_{xy}=L_x\circ L_y$) and $N_{G/F}(x)=x^{[G:F]}$ if $x\in F$ (because then this is the determinant of a homothetic map).
Now if $v^n =u$, then taking the norm $N_{G/F}(v)^n = u^{[G:F]}$. So you may take $\tilde{u}=N_{G/F}(v)$.
The notion of norm map you're trying to use doesn't work if $G/F$ is not a separable extension. Let's write $N$ for the norm you define.
If $G/F$ is not separable, then $|X(G/F)|<[G:F]$ so $N(x)\neq x^{[G:F]}$ for $x\in F$, which would be the expected behaviour to make the proof work.
If $G/F$ is separable then you may see Trace and Norm of a separable extension. for a proof that our two definitions of norm coincide.