It’s supposed to be in the footer, and it’s positioned with CSS. This is partly because at the time that it was introduced there wasn’t a standard hook in themes for placing something at the very top of the page. Instead it is added to the wp_footer hook.
It’s the theme’s job to make sure it accounts for the presence of the admin bar, which it can do using the admin-bar body class that’s added when the bar is present.