Also check that your server isn't setting secure cookies on a non http request. Just found out that my ajax request was getting a php session with "secure" set. Because I was not on https it was not sending back the session cookie and my session was getting reset on each ajax request.
For the record, be advised that all of the above is (still) true only if the AJAX call is made on the same domain. If you're looking into setting cookies on another domain using AJAX, you're opening a totally different can of worms. Reading cross-domain cookies does work, however (or at least the server serves them; whether your client's UA allows your code to access them is, again, a different topic; as of 2014 they do).
According to the w3 spec section 4.6.3 for XMLHttpRequest a user agent should honor the Set-Cookie header. So the answer is yes you should be able to.
Quotation:
If the user agent supports HTTP State Management it should persist, discard and send cookies (as received in the Set-Cookie response header, and sent in the Cookie header) as applicable.
Source: Stackoverflow.com