con php se puede, y con javascript también, pero AJAX no tendría nada que ver, además ignoro si los header sobre cookies enviados por php y recibidos por el XMLHttPRequest tengan efecto.
en fin, con solo javascript basta:
http://www.elated.com/articles/javascript-and-cookies/