No creo que puedas añadir CSS (no lo he probado, aunq en todo caso tendrías que añadir la ruta completa!).
Lo q estoy seguro, es q la etiqueta style sí funciona :)
En la cabezera tienes q añadir el Content-type: html ;)
Código PHP:
$cabeceras .= "Content-Type: text/html; charset=ISO-8859-1\r\n"; //Por ejemplo!