In HTML5, should the main navigation be inside or outside the <header> element?

I do not like putting the nav in the header. My reasoning is:

Logic

The header contains introductory information about the document. The nav is a menu that links to other documents. To my mind this means that the content of the nav belongs to the site rather than the document. An exception would be if the NAV held forward links.

Accessibility

I like to put menus at the end of the source code rather than the start. I use CSS to send it to the top of a computer screen or leave it at the end for text-speech browsers and small screens. This avoids the need for skip-links.

It's completely up to you. You can either put them in the header or not, as long as the elements within them are internal navigation elements only (i.e. don't link to external sites such as a twitter or facebook account) then it's fine.

They tend to get placed in a header simply because that's where navigation often goes, but it's not set in stone.

You can read more about it at HTML5 Doctor.

It's a little unclear whether you're asking for opinions, eg. "it's common to do xxx" or an actual rule, so I'm going to lean in the direction of rules.

The examples you cite seem based upon the examples in the spec for the nav element. Remember that the spec keeps getting tweaked and the rules are sometimes convoluted, so I'd venture many people might tend to just do what's given rather than interpret. You're showing two separate examples with different behavior, so there's only so much you can read into it. Do either of those sites also have the opposing sub/nav situation, and if so how do they handle it?

Most importantly, though, there's nothing in the spec saying either is the way to do it. One of the goals with HTML5 was to be very clear[this for comparison] about semantics, requirements, etc. so the omission is worth noting. As far as I can see, the examples are independent of each other and equally valid within their own context of layout requirements, etc.

Having the nav's source position be conditional is kind of silly(another red flag). Just pick a method and go with it.