Mail > Preferences > General: New message notifications: All mailboxes
Thank you, thank you, thank you. I had asked the same question a while back and had never found a suitable solution. I like having lots of "rules" the segregate my incoming emails into numerous mailboxes.
To the OP: You won't be able to test this by sending an email to yourself as OS X is smart enough to not notify you of a message you sent yourself. I used my wife's iPhone to send my self a message that I knew would be moved to a different mailbox and I was notified as expected.
Now I can sleep good tonight.