Browsers strip the Set-Cookie from XMLHttpRequest-s:
http://www.w3.org/TR/XMLHttpRequest/#the-getallresponseheaders-method
As for Cookies.getCookie(), I think some browsers might wait until the XHR's onreadystatechange (the event that calls GWT's RequestCallback) terminates to update the document.cookies. In other words, it doesn't surprise me much that Cookies.getCookie() doesn't reflect the response's cookie from within the RequestCallback's onSuccess.
If you need the Session ID to send in the client-to-server payload, then I'd suggest you send it in the server-to-client payload as well.