Devi usare un... cookie per ricordarti la scelta.
Se l'utente accetta, crei il cookie che si ricorda l'accettazione, se non accetta non salvi niente e se torna dovrà giustamente riapparire il messaggio.
Visto che si usa un cookie, il messaggio riapparirà anche se l'utente cancella i cookie dal browser.

Comunque, tutto questo va fatto in Javascript per evitare di ricaricare la pagina, che sarebbe fastidioso.