May a page have multiple H1s?

HTML5 allows it, but it helps nobody: two equal-ranked main statements on one page leave open what it's about. For structure and findability, exactly one H1 is the clear solution.

Does the heading in the menu count too?

It counts if it's marked up as a heading element. That's exactly why an H1 in the logo is a problem — it appears on every page and crowds out the page's actual statement.

Does every heading need to contain a search phrase?

No. Headings should describe the section. A structure that works for humans almost always works for search engines too — the reverse isn't true.

This translation has not been editorially reviewed yet. The German version is authoritative. Deutsche Fassung →

Checking headings: exactly one H1 and a hierarchy with no gaps

A page should carry exactly one H1 — the statement of what this page is about — and structure the levels below it with no gaps. Both get checked: the number of H1s, and the order of the levels.

Headings are both an SEO and an accessibility topic. For search engines, they're the content's structure; for screen reader users, they're jump targets: anyone who calls up the heading list gets a table of contents.
The typical mistake in website builders is an H1 in the logo or tagline on every page. Then every page carries the same H1, and the page's actual statement sits in an H2.
Level jumps (H2 straight to H4) are technically possible, but leave a structure full of holes. For orientation, that's the same as a table of contents missing chapter numbers.

Deutsche Fassung — mit allen Prüfpunkten dieses Themas