Generally, while contents that don't fit the screen should be scrolling, controls that affect display or modify content should not. In the "early www", scrolling on-page navigation controls out of view were a result of the limited presentation capabilities, but they also made it simpler: You always scroll the entire page.
The "classic" desktop solution is a non-scrolling region. The in-browser solution of frames or iframes has some usability drawbacks though, e.g. with respect to bookmarking and forward/backward navigation.
The "float animation" draws attention to the navigation controls, in most cases this is excessive in my opinion, as it makes the controls appear more important than the content. (But probably it's the best possible solution). OTOH it is an interesting option to promote new or changed functionality.
From these thoughts I'd conclude: For a nonlinear page with nontrivial controls (i.e. more than just simple page navigation), fixed-location controls are advisable. Try to avoid undue flashiness of the animation involved.