When I was choosing between the two, there was one big difference between the two: notmuch was built around an idea that you mark your messages with tags for organization, while mu assumed you organize stuff into IMAP folders. The notmuch tag database is not a standard IMAP concept, so syncing your IMAP directories wouldn't sync your tags, and moving from one machine to another required extra work. mu by contrast just does the normal IMAP thing, so you sync the IMAP on one machine, and all your other machines can read the IMAP data, and that's it.
I've been using mu for years, and it's fantastic. From personal experience, the tags/folders distinction is mostly immaterial: the vast majority of searches are for text or sender or subject, or something.
If I'm misrepresenting notmuch here, somebody please correct me!