Clearly we cannot keep both the number of $a$'s and the number of $b$'s on the stack, because what order should we use. The solution (I think) is to keep the difference of these numbers on the stack. Or better, the difference between the promised numbers in the DFA computation on word $x\in L$ that we guess, and those that are realised by the word $w$ that we read.

In each step of the computation (i) we read a symbol $a$ from the tape and (ii) follow a letter $b$ in the DFA for $L$. If these letters match then we comtinue. If these numbers differ we increase or decrease the number of symbols on the stack: say we increase that number if $a=0$ and decrease if $a=1$. We accept if the simulated comuptation on the DFA ends in an accepting state ánd the stack is empty (or better represents the number zero).

Clearly we cannot keep both the number of $a$'s and the number of $b$'s on the stack, because what order should we use. The solution (I think) is to keep the difference of these numbers on the stack. Or better, the difference between the promised numbers in the DFA computation on word $x\in L$ that we guess, and those that are realised by the (permuted) word $w$ that we read. The stack is used to count this difference (and we must be able to store both positive and negative numbers).

In each step of the computation (i) we read a symbol $a$ from the tape and (ii) randomly follow a letter $b$ in the DFA for $L$. If these letters match then we comtinue. If these letters differ we increase or decrease the number of symbols on the stack: say we increase that number if $a=0$ and decrease if $a=1$. We accept if the simulated computation on the DFA ends in an accepting state ánd the stack is empty (or better represents the number zero).

PS. This might look different from Yuval's solution, but it basically the same.)