As far as SE rankings go, it may or may not be directly beneficial.
I think the largest benefit is the indirect effect this type of change may have on the overall 'value' of the site.
I think by switching to css you gain a few advantages:
1. Generally, the code is much shorter / cleaner, which will do two things:
A. Help the site to load faster. You might look into calling some graphics from the style sheet while loading others from the html.
B. Change the 'code to visible text' ratio of the site, which may be beneficial to some extent for search engine rankings.
2. Provide a better 'visitor experience', which should directly impact visitor behavior, and reduce the number of immediate 'it's ugly' back clicks to find another search result.
3. Increase 'time on site' / 'page views' prior to another search for the same or a different query. (Slightly different than a 'back click' if you picture a visitor typing a new query, rather than clicking 'back' a number of times to return to the original query and selecting another result. Even if they do click back the time between queries will be increased by increasing page views and usability.)
4. You can generally do a much better job of html tagging, because you have control over the style each tag presents.
So, where you might currently want to emphasize text using an html tag, but choose not to because the 'look' might not be as easy to read, with the use of css you can. For Example: With some font sizes the use of <em> or <i> will cause the text to appear smaller, making it difficult to read, but with the use of css, you can set the size of <i> tags to 1px large than your standard size, making the text appear to be the same size, and easier to read.)
Also, by setting heading tags to the same size, (or the size of your choice for each) you can properly tag headings (easily) from 1 to 6, without having to worry about the 'display size' of each heading, which gives search engines an 'order of importance' for text headings.
5. You have much more control over 'page load order', without the use of 'empty tables / rows / cols' and adjust a page to load from 'most important' to 'least important'. (This is more about communicating with SEs than visitors, by allowing you to load a page (in the source code) in the order a visitor is most likely to read, which, when combined with proper heading tags can help indicate 'order of importance' of topics to a search engine.)
There are a few more reasons I opt for css, but those are the main ones.
As far as change over, I personally use 'all at once', just because it says, 'new template' and makes a site easier for visitors to use, since they only need to get used to one style / format. (It's also generally easier to use a bulk 'find / replace' to make sure I don't miss anything than to try to make changes by hand, or in 'sections'.) I'm not sure how much it matters from a SE perspective, but prefer a site be consistent for visitors.