Para definir una cookie, tienes que establecerla antes de cualquier operacion en tu página, incluso la existencia de un espacio antes de <html> te daría un error.
Los errores que comentas se producen porque el navegador ha recibido información de cabeceras y al intentar establecer la cookie despues de esta información dispara el error.
Cuando establezco una cookie, yo uso algo como lo siguiente en mis ficheros.
Código PHP:
<?php
//Genera una cookie que permite al usuario descargar ficheros desde el site
$Nombre = "Descargas";
$Valor = "www.midominio.com";
$Expira = mktime(0,0,0,7,20,2005);
$Domain = "midominio";
setcookie($Nombre, $Valor, $Expira, $Domain);
//Establecer la cookie de control para el registro
if($tp == "19") setcookie("registro", "estado=1", time() + 3600, "/", "midominio.com", 0);
RESTO DEL CODIGO PHP
//La variable $tp="19", es una variable de control que uso en el sitio de uno de mis clientes, y que para el ejemplo no tiene relevancia.
establecería una cookie que espira al cerrar el navegador o cambiar de página.