g1smd - 10:30 am on May 15, 2011 (gmt 0)

It varies and can take anything from a few days to many months. You'll likely see a dip in traffic to begin with. The new URLs usually start to appear within days, and it takes a few months for the old ones to drop out.

One important question. Will you be reversing a www to non-www redirect, OR have you simply been linking to non-www with NO redirect in place and now you are going to link to www AND place a non-www to www redirect at the same time?

Whatever you do, you must change the links on the pages so that clicking any internal navigation link never results in a redirect.

At the same time, make sure you're linking to "/" or to "/folder/" and NOT to a named index file. Install the standard "index" to "/" redirect too (it goes before the non-www to www redirect).

These searches are useful:
site:example.com -inurl:www
site:www.example.com
Make sure the site root is the first result in the list.