Ugh, by default Mail.app just searches in the current mailbox. When you start a search, on the top of the left sidebar, just above your list of mailboxes, a new “All Mailboxes” folder will appear. Click that to search the whole app.

I don’t know why they did this. I don’t know who was asking for it.