Depends, session_start needs to be called before any output occurs or you'll get an error.
If your header include contains everything that would be between the header tags on the page, what is creating the container html? If your code looks like the following and you put the session start in the header include, it will error out, as the html is being sent to the browser before the session starts.
session_start(); is my first statement as a rule. UNLESS I have a common file included in every page, which is usually the case, e.g. config.php, so I put the session_start() at the top of that file instead and ensure that that file is included as a first statement:
This ensures that the session_start() is included.
Either if it is the first thing to appear in the file - either directly in the file itself or from your include file (if the include file is the first thing to appear in the file and the session_start is the first thing to appear in the include file). It shouldn't make any difference. Technically, I don't think it matters if it is the first thing, just as long as there is no html output.