Given L is a regular language, prove that Perm(L) is Context-Free
For every symbol $\sigma_i$ that the PDA reads, it guesses a symbol $\tau_i$. It simulates the DFA on the word $\tau_1 \ldots \tau_i$, and will only accept if the DFA accepts. Using the stack, it maintains the following counter:
$$
(\#_a(\sigma_1 \ldots \sigma_i) - \#_b(\sigma_1 \ldots \sigma_i)) - 
(\#_a(\tau_1 \ldots \tau_i) - \#_b(\tau_1 \ldots \tau_i)),
$$
and only accepts if this equals zero at the end. Since
$$
\#_a(\sigma_1 \ldots \sigma_i) + \#_b(\sigma_1 \ldots \sigma_i) = 
\#_a(\tau_1 \ldots \tau_i) + \#_b(\tau_1 \ldots \tau_i),
$$
the counter equals zero iff $\tau_1 \ldots \tau_i$ is a permutation of $\sigma_1 \ldots \sigma_i$ (this only works because the alphabet is binary).
To see that this approach doesn't work for a ternary alphabet, it suffices to consider
$$
\operatorname{Perm}((abc)^*) \cap a^*b^*c^* = \{ a^nb^nc^n : n \geq 0 \}.
$$