Os índices são usados para optimizar a tua base de dados. Por isso, boa parte dos problemas de desempenho em uma BD se resolvem com índices bem construídos. 

Assim como os livros, que são um conjunto de capítulos com muitas páginas cada, os bancos são conjuntos de tabelas como muitos registros cada. Em ambos nós precisamos ter índices, que são estruturas de apoio para encontrar rapidamente o que estamos procurando.

Note que índices e chaves são coisas diferentes, embora a chaves primárias sejam os únicos índices clusterizados das tabelas. 

Primeiro, toda tabela deve ter um índice clusterizado, que é o índice que rege a ordenação das linhas da tabela. Ou seja, a chave primária. Fora as regras tradicionais de chaves primárias, como não poder haver repetição, dê preferência por usar um campo numérico como chave, pois os índices trabalham melhor como estes campos (i.e. as consultas serão mais rápidas). Este é o mais básico e elementar dos índices e ele é criado mesmo que você não saiba disso.

Segundo, crie índices nas suas chaves estrangeiras. Não necessariamente em todas, afinal o uso excessivo de índices prejudica a performance dos INSERTs, UPDATEs e DELETEs, mas nas FKs que você costuma fazer JOIN.

Terceiro, crie índices para garantir integridade. Quando você cria um índice para uma coluna (ou grupo delas) e diz que ele é UNIQUE, você não apenas garante que não haja elementos repetidos em sua tabela, como aumenta significativamente a performance de consultas que envolvam as colunas do índice. Isso porque quando o motor de consulta do SQL Server sabe que um campo não se repete, ele vai parar de procurar por mais ocorrências daquele campo tão logo encontre a primeira ocorrência, entende?

Quarto, dê manutenção nos seus índices periodicamente. Conforme você vai inserindo, removendo e atualizando elementos da sua tabela, seus índices vão ficando fragmentados, o que pode prejudicar a performance de uma maneira até pior do que a ausência de índices. Desta forma, lembre-se de dar um Rebuild nos seus índices quando eles estiverem fragmentados, preferencialmente em horários de pouco acesso ao seu sistema para evitar problemas com os usuários.

CREATE INDEX nomeIndex ON nomeTabela(campo à Indexar)

Ex: Temos a tabela ItemVenda(idItemVenda,idProduto,quantidade,subTotal,IdVenda) e queremos indexar o campo IdVenda.

CREATE INDEX ixIdVenda ON ItemVenda(idVenda)

ALTER INDEX {nomeIndex | all} ON nomeTabela REBUILD

ALTER INDEX {nomeIndex | all} ON nomeTabela REORGANIZE

Escolha uma dessas instruções para colocar os índices da tua base de dados sempre estáveis.