Las llamadas a session_start() así como muchas otras cosas deben hacerse antes de cualquier tipo de salida, y tu precisamente caes en ese error.
En tu localhost "funciona" porque tiene más configurado tu ambiente, y jamás deberías asumir que va a funcionar bien en todas partes.
Por favor lee el manual de sesiones al respecto:
http://www.php.net/manual/es/book.session.php