Nem sempre é claro onde usar índices em tabelas SQL. Mas existem algumas regras gerais que podem ajudá-lo a decidir na maioria dos casos.

1. Coloque o índice nas colunas que estão sendo usadas nas cláusulas where
2. Coloque o índice nas colunas que você usa para unir.
3. Tente não usar mais de 4 a 5 índices nas colunas da mesma tabela.

E os conceitos gerais que você deve ter em mente são:

1. Qualquer índice que você usar tornará as pesquisas nessas colunas mais rápidas.
2. Qualquer índice que você adicionar fazendo com que a inserção nesta tabela seja um pouco mais lenta.
3. Dos dois anteriores. É sua responsabilidade decidir quantas inserções e consultas você faz nas tabelas para decidir se deve usar o índice e em quais colunas ou não.

EDITAR

O comentário do @AndrewLazarus é muito importante e decidi adicioná-lo à resposta:

1. Não use índices em colunas com apenas alguns valores diferentes. Por exemplo, uma coluna que contém um estado, quando há apenas alguns estados, ou um valor booleano. A razão para não fazer isso é que o índice realmente não ajuda você, pois ele será dividido apenas pelo número de valores, e como você tem apenas alguns deles, não haverá nenhum benefício real. A tabela consumiria mais espaço com o índice e seria mais lenta na inserção, mas você não obteria um desempenho significativamente melhor durante a consulta