Um bom software oferece mais de uma forma de alcançar o mesmo resultado. Assim, cada usuário pode desenvolver sua técnica, com a ferramenta que lhe for mais confortável. Para remover o fundo de uma imagem no Photoshop você tem alguns caminhos, dos mais simples (e de acabamento duvidoso) aos mais complexos, que quase sempre terminam melhor.
Vamos escolher algumas imagens e entender porque nem sempre dá pra limpar o fundo, pelo menos não sem perdas ou dificuldade, enquanto outras são barbada.
Fundo de cor sólida
São as mais fáceis. Não importa se a cor é branco sólido, ou um azul de céu limpo, desde que seja o mais uniforme possível. Até quem nunca abriu o Photoshop consegue remover com as ferramentas básicas.
A Varinha Mágica é a opção mais simples e lembrada. Quanto mais definidos os contornos do objeto a ser recortado, melhor o resultado. Se o fundo for de cor única, como um céu azul, mas houver elementos como cabelos soltos ou pelagem animal, a Varinha não funciona bem.
Exemplo:

Nessa imagem, toda a área azul é bem delimitada, sem degradês, então a Varinha Mágica resolve com um clique.
Já nessa:
Pela delicadeza dos fios, é virtualmente impossível obter uma boa seleção com a Varinha Mágica, sendo preciso recorrer a outras técnicas. Falamos sobre seleção de cabelos aqui.
Se a foto tem detalhes complexos como folhas, penas, etc, mas o fundo é predominante numa cor, a seleção Intervalo de Cores costuma dar ótimo resultado.
Digamos que quero substituir o fundo dessa imagem:

Com ela aberta no Photoshop, siga ao menu Selecionar > Intervalo de Cores. Na janela aberta, aparece a máscara da futura seleção — a parte mais clara será selecionada. Clique uma vez em alguma parte do fundo pra pegar a cor.
Procure uma cor que alcance o máximo de fundo, com o mínimo do assunto.
Arrastando a barra Grau de Seleção você terá diferentes seleções, com mais ou menos tons próximos ao que foi escolhido com o Conta-Gotas.
No caso do passarinho, se aumentar demais o grau, a seleção incluirá partes de sua cabeça. Note na imagem em preto e branco (a máscara) como um “brilho” é visível no alto da cabeça e mais ou menos na região dos olhos. Se você confirmar a seleção assim, ela se espalhará por quase todo o fundo, mas também naquela parte da ave.
Caso não seja possível eliminar esses pontos com a barra de grau, confirme a seleção…
pressione a tecla Q uma vez…
e será mostrada a máscara da seleção. Todas as partes vermelhas estão FORA do que será selecionado.
Com um pincel redondo (tecla B), pinte em preto para remover essas regiões da cabeça da seleção. Na verdade, você estará não pintando de preto, mas trabalhando na máscara.
Se o fundo tinha a cor irregular e pontos dispersos continuaram fora da seleção…
é parecido, mas em vez de pintar de preto, use branco e as áreas entram na seleção.

Quando terminar, pressione Q outra vez.
Se quiser apenas remover o fundo, pressione Delete uma vez e adeus fundo.
Se quiser enviar o fundo para outra camada, em vez de pressionar Delete, use o atalho Ctrl + J (nova camada por cópia). Se quiser enviar a parte não selecionada (o pássaro) para outra camada, primeiro inverta a seleção (atalho Ctrl + Shift + I), então use o atalho anterior.
Agora podemos inserir outra imagem e alterar o fundo, adicionando um céu:
Pra ficar mais natural, faltam ajustes como correspondência de cor, senão virá o efeito “recortado”, como acima: parece um boneco de papel sobre aquele fundo bacana. Mas essa é uma forma excelente de remover fundos.
Mais um exemplo
Seguindo o método acima, mas corrigindo as cores.
Em certas imagens, as cores estão espalhadas entre o fundo e o objeto que você quer separar. Veja como há verde no fundo e sobre o animal, da luz ambiente refletida na vegetação:

Nesse, é impossível obter uma boa seleção só pelo intervalo de cores (verde). O esquema de pintar sobre a máscara é fundamental para reduzir a seleção só ao fundo.
O resultado com o novo fundo:
Como na ave, a cor sobre ele destrói qualquer ilusão de profundidade. Veja como melhora com um simplíssimo ajuste no verde, alterado para azul:
Só foi pintado em azul sobre o pescoço e maxilar do animal em modo “Matiz”, com a mesma cor do céu.
Na força bruta…
Se as ferramentas simples não colaboram, o jeito é apelar às técnicas complicadas. A mais precisa — e trabalhosa — é a Caneta. Cria-se ponto por ponto, como num jogo tipo “ligue os pontinhos”, e no final, converte-se o demarcador criado em seleção. Leia Como criar demarcadores e seleções no Photoshop.
E é bom lembrar que nem toda imagem é adequada para troca de fundo, pela riqueza de detalhes, posições difíceis de recortar dos objetos, etc. Algumas beiram o impossível.