For the longest time, I thought notmuch did not support indexing the body of encrypted emails. This was quite the inconvenience since I could never properly search for emails from my encrypted correspondents. But finally, I figured out that you have to set index.decrypt to true in your ~​/.notmuch-config. See the man page of notmuch-config for more. Once set, all encrypted mail will be indexed from now on. To reindex all older email, run notmuch reindex '*'.

The index section of your ~​/.notmuch-config should look something like this.

[index]
decrypt=true