Il session_start e il set_cookie modificano gli header della pagina, quindi devono essere messi prima.
Io ti consiglio, appena il cliente effettual il login (quindi nella pagina del login) di creare un uniqid, e hasharlo con md5 o roba del genere.
Lo salvi su database e lo metti nel cookie.
Appena il cliente ritorna, se ha il cookie, cerchi l'uniqid nel database. Se lo trova vuol dire che si può loggare e setti tutte le sessioni in modo da non dover più richiamare il database.