What are some good ways to incorporate a 728x90 ad into the header of a site keeping the navigation in mind?
Banner ads don't receive anything like the click through rate that they used to. In fact users have often programmed themselves to ignore banners such as the leaderboard size that you mention, especially in the top header position. The very size of the block alone will deter users - let alone the content, even if it is well designed.
For this reason, the header is no longer the optimal position - it's in-line with the content itself. And much it pains me to write this because of course that's the most annoying place for users to find ads. I've noticed this positioning is trending upwards amongst more and more of the websites I visit, but very often with such poor implementation that my view of the websites in question immediately takes a nose dive, and I leave. Usually the most annoying position I find is actually in the middle of content.
Thus it is more and more important not to make cheap and annoying banners (that do the hosting website a disservice) but instead to produce interesting, attractive, clever, well designed advertising spaces that attract the eye for more reasons than by distraction (aka annoyance) alone.
In response to your question, I don't think it's answerable in terms of there being a good way to do it - due to both the desired position (in the header) and the dimensions (the ubiquitous leaderboard).
When positioning in-line with content, I think it would be best to place it under the navigation - before the content proper, and not actually interrupting the flow of content (reducing the annoyance factor)
Here is an ironic example of a banner (albeit an appeal banner rather than an ad banner) used on the Wikipedia article for web banner. Also, notice the discrete ability to close the banner - putting the user a little bit back in control.
In as much as it is possible to like an ad, I actually quite like the simplicity that goes with the brightness of this pingdom ad, which does sit between the global and local navigation bars.
At first impression it looks like it's part of the header for the website I'm visiting but in actual fact it's an ad for pingdom. It almost seems to designed to be a similar height to the logo of the site I'm visiting and fits neatly in position, making it belong. The tagline looks like it is related to the website rather than the ad, which perhaps allows you to start to engage (visually) with the banner more than you might otherwise.
I'm not sure that all that is deliberate, but for me at least it appeals more than most - or perhaps that should read: it annoys me less than most!