Como você suspeitava de seu assunto, a variável PATH precisa ser atualizada corretamente.
Se você estiver usando bash como seu shell, isso pode ser feito no seu arquivo pessoal ~/.bashrc ou nos arquivos globais /etc/profile ou /etc/bashrc para todos os usuários. Você adicionaria uma linha como essa nos dois casos:
PATH=$PATH:/path/to/php/directory/