Asaf, what you are saying is false. In $L[\mu]$, for example, there is a unique normal ultrafilter. (Unless I misunderstand. You are saying that for every $S$ stationary-costationary, you can find a normal $U$ with $S\in U$, right? Obviously, any normal $U$ satisfies that either $S$ or $\kappa\setminus S$ is in $U$, which is what you wrote.)
Edit : This is a nice homework problem. There are several different solutions, and you may want to study them afterward. Here is a way of thinking about this; it is perhaps not the most efficient, but it is very useful. Suppose $U$ on $\kappa$ is normal and concentrates on measurables. Then $\kappa$ is measurable in $M$, where $j:V\to M$ is given by $U$. So there is a normal $U'$ on $\kappa$ in $M$, and $U'$ really is normal (in $V$, not just in $M$). Let $k:V\to N$ be given by $U'$. what can you say about the sizes of $j(\kappa)$ vs $k(\kappa)$ ?
Here is another approach: Use induction, use that you are at a measurable (so you have a normal $U$) and "integrate" the measures on small cardinals witnessing the claim. Check that the resulting measure is as you want.
Let me add a couple of details to the first approach (I know it is more elaborate than the other one, but the payoff is worth the effort):
If $j:V\to M$ is the ultrapower embedding by a normal measure $U$ on $\kappa$, then ${}^\kappa M\subset M$ and from this it is easy to check that if $M\models$"$U'$ is a normal measure on $\kappa$", then $U'$ is a normal measure on $\kappa$ in $V$.
Now, suppose that $U$ concentrates on measurables. Since the identity represents $\kappa$ in $M$, it follows that $\kappa$ is measurable in $M$, and there is $U'$ as mentioned.
Essentially, we want to iterate this process: Form the embedding $k:V\to N$ given by $U'$, and if $U'$ concentrates on measurables, then we get $U''$ in $N$ and form $l:V\to P$, etc. We would like this process to stop after finitely many times. For this, we want to associate to a normal measure $U$ on $\kappa$ an ordinal $\alpha_U$ in such a way that if $U'$ is in the ultrapower by $U$, then $\alpha_{U'}<\alpha_U$.
The easiest way to do this is to set $\alpha_U=j(\kappa)$. If $U'\in M$, we can form in $M$ the ultrapower embedding by $U'$, call $k'$ the result, so $k':M\to M'$, and recall we called $k:V\to N$ the ultrapower of $V$ by $U'$. The point is that $k'(\kappa)=k(\kappa)$, because ${}^\kappa M\subset M$, so all functions $f:\kappa\to\kappa$ are in $M$, and this and $U'$ is all we need to compute the value of the embedding at $\kappa$.
But $M\models$"$j(\kappa)$ is inaccessible, while $k'(\kappa)<(2^\kappa)^+$", so $k'(\kappa)
A posteriori, this argument shows that the relation $\prec$ on normal ultrafilters on $\kappa$ given by "$U'\prec U$ iff $U'$ belongs to the ultrapower by $U$" is well-founded, and so we can assign to $U$ the ordinal $o(U)$ given by its rank in this well-founded relation. This is Mitchell's ordering, and it is a very useful tool in large cardinal theory.