Julio Queiroz Matos, bom dia.
Certo, vamos lá tentar te ajudar:
Eu preciso emitr NF ou CRTC?
NF é para venda, a empresa irá transportar. Quem deve emitir a NF é quem contratar a empresa do seu futuro cliente. E se tratando de operação interestadual será a
NFe e não NF.
CTRC está abolido. A emissão será do CTe.
Eu preciso ter uma filial pra emissão em cada estado?
Em teoria não. Porém isso depende muito de estado para estado. Somos de SP e tínhamos uma empresa que transportava de SP para MS, de maneira contínua, para a Eldorado Brasil e o Posto Fiscal de MS, percebendo isso, quis obrigar a inscrição da empresa no estado. Após algumas conversas diretas entre PF e Eldorado, foi elaborado um Regime Diferenciado para as empresas prestadoras de serviços para a Eldorado que não tinha IE no estado do MS, que deixou de exigir a inscrição do estado.
Além de
CNPJ, Inscrição Estadual e Municipal eu preciso de algo a mais para operar?
Consigo lembrar aqui agora também do registro na ANTT e, caso o seu município exija mais algo em relação a esta atividade também né. Isso terá que verificar diretamente com a PM de Embu, caso for ai que a empresa seja constituída.
Tem um material bem legal
nesse link. Só não sei se está bem atualizado. Sabe como é a legislação nesse país e no estado de SP né.