I'm a former editor, and generally speaking, you can legally put the following year's copyright date on your books as of August. Usually the 2006 titles come out in August 2005 in preparation for the Fall/Christmas season. I'd say look at bookstore's shelves mid- to late August.
If you pre-order on-line (amazon.com or the likes), they'll ship it as soon as it's available.
I should add... that's of course if the editors are on schedule