It doesn't sound like they're switching to rendering on the backend, though. So you're most likely still going to have to execute a huge chunk of javascript before displaying the page, though hopefully it will get faster.
A page with a single tweet on really shouldn't need to pull down much code. The JS can all be cached by the browser (far future expires headers etc) and there are some neat tricks you can do with app cache and localStorage to make that work even better.
At the moment if you go to https://twitter.com/#!/twitter then it loads up the HTML for https://twitter.com/, if you're logged in it will be the tweets of those you follow. Then the javascript magic loads in @twitter's profile dynamically.
PushState will allow twitter to load in the static HTML for @twitter's profile at https://twitter.com/twitter/ and then progressively enhance it with javascript. The net gain will be that the page will be available much faster on initial page load.
Twitter is sending down the home timeline as HTML. In fact, what most people are looking for when they go to twitter.com is their home timeline so I'm correct, this is what they are doing (at least in new-new-twitter which I think almost everyone now has). You're also correct, when you go to twitter.com/#!/n8agrin you get your timeline in the background which is then replaced with my tweets. However it wasn't always this way. At one point in time, going to twitter.com just downloaded a bunch of javascript and an HTML bootstrap. The whole site was generated by javascript. I know this because I worked on it.
Technically pushState doesn't really have anything to do with the practice of progressive enhancement or making anything "much faster". You can make pure javascript sites very fast, you can make serving straight up HTML very fast, you can progressively enhance HTML without pushState. pushState is really just a way to manipulate the history of a browser, while optionally changing the browser's current url, without a page refresh (read more here: https://developer.mozilla.org/en/DOM/Manipulating_the_browse...). You can use it to do a lot of things, one of which is to have it serve as one part of a solution for sites that behave like single-page apps without having to resort to the fragment identifier (http://en.wikipedia.org/wiki/Fragment_identifier), forever vilified as the hashbang.
Most sites these day (including Facebook, Gmail, etc) have to execute "a huge chuck of js" before displaying the page.
I have been told by some people in the know that they have come up with a system similar to pjax for certain page components, though that may have changed.
By way of comparison, view the following two links in a javascript-less browser (or just view source):
$ w3m http://twitter.com/#!/danwrong/status/171680703824662528
$ w3m https://plus.google.com/117377434815709898403/posts/f35f8QvHab7
This is a good move by Twitter. I wholeheartedly endorse it.
They'd just serve the exact same (static) html for every twitter.com/username URL. I don't think it's exactly terrible Javascript hackery to look at the location.href and do an ajax call.
They'd probably support web crawlers with the same system they use now. And many web crawlers these days execute javascript anyway.