Werden wirklich keine Cookies erstellt? Oder rätst Du das, weil Du die PHPSESSID in der URL siehst?
Die URL wird auch so dargestellt, wenn Du auf zum ersten Mal auf eine Seite kommst und in php.ini der Wert von session.use_trans_sid auf 1 steht. Das mußt Du auf 0 stellen, wenn Du das Verhalten ändern willst. Das Problem ist dann aber, wenn Browser keine Cookies akzeptieren, dass dann Sessions gar nicht mehr funktionieren. Denn Cookies werden (wenn es geht) dennoch angelegt, selbst wenn Du die PHPSESSID im Browser sehen kannst. Man kann das überprüfen, indem man auf einen Link klickt, in der Folgeseite sollten dann endgültig in den Links die PHPSESSID verschwunden sein - weil dann ein Cookie vorhanden ist.
Zusätzlich solltest Du den Wert von session.use_cookies nachschauen, der muss natürlich 1 sein, sonst werden erst gar keine Cookies angelegt.
Und Last not Least kann man das alles auch selbst nachlesen in der hervorragenden Dokumentation auf
www.php.net