O que são efeitos colaterais?

O efeito colateral é o fenômeno que interfere em uma situação além do esperado, que acontece algo por consequência do evento principal. Em computação é isso também, e usamos para dizer que um código afeta algo que está além dele. Isso ocorre quando algo não é autocontido, que falta encapsulamento (no sentido amplo da palavra, não no que normalmente é indevidamente usado em OOP). Em muitos casos falamos deles como contrativo de "efeito colateral escondido" e geralmente ele tem uma conotação negativa, já que é algo que afeta o ambiente externo sem que seja sua intenção.

Nesse contexto mostrado na pergunta é claro que significa isso, mas com uma especificidade maior. Ali indica que no funcional um código não altera estado externo a ele. Então ele pode ter estados locais e até alterá-los sem problema, ele pode receber estados externos, mas não pode alterar estes estados recebidos.

Se alterar um estado externo à uma função está gerando o efeito colateral. E não importa como vem esse estado esterno, pode ser por parâmetro normal, pode ser por parâmetro implícito (normalmente o this), ou pode ser porque este estado está visível globalmente, incluindo dado que vem de fora da aplicação. OOP praticamente força você fazer isso.

Mas receber um dado externo sem alterá-lo é algo normal e não causa efeito colateral. Alterar uma cópia local de um dado é tranquilo e "puro". Claro, há sempre um dificuldade local quando altera este estado, mas isso não é considerado efeito colateral por ser autocontido.

Alteração de estado é uma das coisas que mais criam problemas na computação, o ideal é evitá-lo tanto quanto possível, ou pelo menos limitá-lo a um escopo bem específico. Funções que não alteram estado externo são mais simples de escrever, entender e depurar, mas claro nem sempre isto é possível, e como tudo é trade-off, tentar fugir do efeito colateral exageradamente chega complicar mais ainda em muitos casos, por isso linguagens que tentam ser puras (onde dá) são muito complicadas para a maioria das pessoas. Por outro lado fortalece a ideia de alterar estado externo, um dos motivos que o paradigma é mais criticado. O que muitas vezes poderia ser só comunicação externa sem alteração de estado vira efeito colateral sempre.

Só lembrando que zero efeito colateral é impossível em qualquer código não trivial. E a programação funcional de quase todas linguagens evitam essa pureza a qualquer custo, apenas incentivam que ela seja assim.

É possível evitá-los em orientação a objeto, mas na verdade deixa de ser OO pelo menos naquele ponto :) Claro, tem métodos que não alteram estado do objeto que ele pertence ou objeto externo, então esse método não tem efeito colateral, mas não é o normal em OOP e em geral isto ocorre apenas por coincidência.