You should always:
- Remove his/her SSH-Key
- Change all passwords he knew
- Lock all his/her accounts on all services
- Give certain services extra attention, e.g. mail forwarding rules
Some other measures you should consider, depending on the circumstances, how much you trusted him or her and your resources:
- Let another person with the same knowledge check if the leaving person installed any backdoors on workstations or servers.
- Run routine scans for vulnerabilities you took as inexistent and which can be created on purpose in a short time, like SQL-Injection possibilities.
- Check all workstations and servers he had access to physically for keyloggers and other malicious hardware.
- Change the locks the person had keys to, you can't know if copies were made.
As a precaution it's good to synchronize HR with IT. Make sure that one person can de-activate all accounts at the moment the employee leaves his workstation to go meet with HR. At the very least change his passwords to stop him from accessing the network as he exits HR.