Internet Explorer's High Privacy setting "blocks all cookies from websites that do not have a compact privacy policy." This includes out-of-the-box installations of Drupal 7.
Here's a work-around:
Add
header('P3P: CP="We do not have a P3P policy"');
to your settings.php file. Tested with IE9.