Can CSS truly override the order of HTML elements on a page?

CSS can take elements out of the normal flow and position them anywhere, in any manner you want. But it cannot create a new flow.

By this I mean that you can position the last item from the html document at the beginning/top of the page/window, and you can position the first item from the html document at the end/bottom of the page/window. But when you do this you can't position these items relative to each other; you have to know for yourself how far down the end of the page will be for the first item from the html document to be positioned correctly. If that content is dynamic (ie: from a database or CMS), this can be far from trivial.

With Floating, and with position absolute, you can pull some pretty good positioning magic to change some of the order of the page.

For instance, with StackOverflow, if the markup was setup right, the title, and main body content could be the first 2 things in the markup, and then the navigation/search, and finally the right hand sidebar. This would be done by having a content container with a top margin big enough to hold the navigation and a right margin big enough to hold the sidebars. Then both could be absolutely positioned in place. The markup might look like:

h1 {
  position: absolute;
  top: 0;
  left: 0;
}

#content {
  margin-top: 100px;
  margin-right: 250px;
}

#nav {
  position: absolute;
  top: 0;
  left: 300px;
}

#side {
  position: absolute;
  right: 0;
  top: 100px;
}

<h1> Stack Overflow </h1>
<div id="content">
  <h2> Can Css truly blah blah? </h2>
  ...
</div>
<div id="nav">
  <ul class="main">
    <li>quiestions</li> ... </ul>
  ....
</div>
<div id="side">
  <div class="box">
    <h3> Sponsored By </h3>
    <h4> New Zelands fish market </h4>
    ....
  </div>
</div>

The important thing here is that the markup has to be done with this kind of positioning magic in mind.

Changing things so that the navbar is on the left and the sidebar below the nav be too hard.

You may want to look at CSS Zen Garden for excellent examples of how to do what you want. Plenty of sample layouts via the links on the right to see the various way to move everything using strictly CSS.