Back in the day of Magento CE 1.3, I would say, definitely… install the Yoast module.. it gave you canonical URLs, and a few other things which were not supported by Magento out of the box. Now, a few years later, Magento has all everything we used the module for. Canonical URLs, although disabled by default, are supported for those that need/want them.
Magento comes with pretty decently constructed markup for SEO purposes out-of-the-box. Saying this here, I kind of expect to irk some discussion, but I'll risk it. No, it's not the absolute best, but the larger problem is the content being put into a new site.
Also to point, the term SEO == Search Engine Optimization. Just like you cannot optimize code for performance until it's been written, you can't optimize a site for search engines until it's been indexed and you can see where things fall. However, that's not to say you can't follow best practices! :)
I'll be honest, I do not remember the last time we installed a module for SEO enhancements on a client's website. We have, however, recommended against installing them where a client asked us about whether they should install something off-the-shelf which they found on Connect.
If canonical URLs are needed, we turn them on. If markup needs to be changed to fit the content better, we alter the (typically highly custom) theme's templates to contain the necessary changes. I would much rather see the site and it's content looked at critically and custom / targeted changes being made than any SEO "module" be installed, which is IMO worse since it blindly introduces sometimes unknown and irksome changes into the site.
My final advice: focus on getting your taxonomy correct the first time so you don't have to restructure it two-months after launch, make sure the copy on your site isn't going to introduce a lot duplicate content, setup proper meta tags, keywords, etc. And lastly (but certainly not least) make sure you get a complete list of all URLs on your existing site and setup proper 301 redirects so you don't get penalized for suddenly 404'ing content.