The terms which provide both licenses existed at least back to 2010-06-09, which is the first capture I'd previously found on archive.org of the Terms of Service:
You agree that all Subscriber Content that You contribute to the Network will be licensed under the Creative Commons Attribution Share Alike license. You grant Stack Overflow the right and license to use, copy, cache, publish, display, distribute, modify, create derivative works and store such Subscriber Content and to allow others to do so (“Content License”) in order to provide the Services.
That version probably existed at least one day prior to that capture, as the capture for http://stackoverflow.com on 2010-06-08 has a "legal" link at the bottom. However, the capture for 2010-06-05 doesn't have a "legal" link.
There may have also been some licensing information placed in questions tagged "faq", potentially on the main site or Meta Stack Overflow. However, I didn't see anything linked from the homepage in earlier captures which gave me the impression that something else was "obviously" in place.
If you trace the history back, the location of the Terms of Service bounced around a bit, first in a couple of locations on stackoverflow.com, then on stackexchange.com, and later on all sites.