Usa
http://hpneo.github.io/gmaps/, que no necesita cookies porque sólo trae DIVs e imágenes de google maps.
O si quieres seguir con tu sistema, ese trabajo lo tiene que hacer PHP y javascript. Cuando el usuario cierre el aviso flotante, manda una petición ajax al servidor para que almacene en la sesión que el usuario aceptó o no las cookies. Y cada página debe comprobar en la sesión si esa información existe. Si no existe, dibuja el menú flotante. Y si existe, dependiendo de si está a TRUE o FALSE tendrás que hacer cosas diferentes.