How do I save session data for the anonymous users?
It because drupal save session with key, this mean you should do something like 

  $_SESSION['yourkey']['xxx'] = serialize($data);


You can try this.

function lists_session($key, $value = NULL) {
  global $user;

  static $storage;

  // If the user is anonymous, force a session start.
  if(!user-&gt;uid) {
    drupal_session_start();
  }

  if ($value) {
    $storage[$key] = $value;
    $_SESSION['lists'][$key] = $value;   // I use 'lists' in case some other module uses 'type' in $_SESSION
  }
  else if (empty($storage[$key]) &amp;&amp; isset($_SESSION['lists'][$key])) {
    $storage[$key] = $_SESSION['lists'][$key];
  }
  return $storage[$key];
}


So, to save a variable in Session:

lists_session("xxx", serialize($data));


And to retrieve the value, just use:

$myVar = lists_session("xxx");


and aslo as MOLOT mentions sometimes session not stareted for anonymous users then you should drupal_session_start() manually.