Las cookies son pequeños archivos de texto generados por los navegadores que se guardan localmente en tu ordenador y que almacenan información necesaria para su funcionamiento. Pueden ser datos de sesión (por ejemplo, para guardar los datos de identificación o el carro de compra de una tienda virtual), de preferencias de usuario, etc...
Estos pequeños ficheros tienen un "tiempo de vida" determinado (p.e. los datos de sesión normalmente se eliminan al cerrar el navegador), pero en algún caso pueden ser permanentes. En estos casos, si hay un cambio en la web y los nuevos datos no coinciden con los almacenados, pueden aparecer conflictos.
En cualquier caso, las cookies se pueden eliminar cuando el usuario desee (en Firefox, en la configuración de privacidad, p.e.).
Más info: http://es.wikipedia.org/wiki/Cookie_%28inform%C3%A1tica%29