The very best advice I have ever found:
(I forget who wrote this but I am posting it knowing that this advice will certainly help you!)
The EVIL Lecture
It's really, really, really hard. It requires a very complete audit. If you're very sure the old person left something behind that'll go boom, or require their re-hire because they're the only one who can put a fire out, then it's time to assume you've been rooted by a hostile party. Treat it like a group of hackers came in and stole stuff, and you have to clean up after their mess. Because that's what it is.
Audit every account on every system to ensure it is associated with a specific entity.
Accounts that seem associated to systems but no one can account for are to be mistrusted.
Accounts that aren't associated with anything need to be purged (this needs to be done anyway, but it is especially important in this case)
Change any and all passwords they might conceivably have come into contact with.
This can be a real problem for utility accounts as those passwords tend to get hard-coded into things.
If they were a helpdesk type responding to end-user calls, assume they have the password of anyone they worked with.
If they had Enterprise Admin or Domain Admin to Active Directory, assume they grabbed a copy of the password hashes before they left.
If they had root access to any *nix boxes assume they walked off with the password hashes. Also reset any public-key SSH keys that may be in use for root-login SSH (don't do that at all, but if you have it, clear 'em).
If they had access to any telecom gear, change any router/switch/gateway/PBX passwords. This can be a really royal pain.
Fully audit your perimeter security arrangements.
Ensure all firewall holes trace to known authorized devices and ports
Ensure all remote access methods (VPN, SSH, BlackBerry, ActiveSync, Citrix, SMTP, IMAP, WebMail, whatever) have no extra authentication tacked on, and fully vet them for unauthorized access methods.
Ensure remote WAN links trace to fully employed people, and verify it. Especially wireless connections. You don't want them walking off with a company paid cell-modem or smart-phone. Contact all such users to ensure they have the right device.
Fully audit internal privileged-access arrangements. These are things like SSH/VNC/RDP access to servers that general users don't have, or any access to sensitive systems like payroll.
Start hunting for logic bombs.
Check all automation (task schedulers, cron jobs, or anything that runs on a schedule) for signs of evil. By "All" I mean all. Check every single crontab. Check every single Windows Task Scheduler. Even workstations.
Validate key system binaries on every server to ensure they are what they should be. This is tricky.
Start hunting for rootkits. By definition they're hard to find, but there are scanners for this.
Not easy in the least. Justifying the expense of all of that can be really hard without definite proof that the now-ex admin was in fact evil. The entirety of the above may not even be doable with company assets, which will require hiring security consultants to do some of this work.
If actual evil is detected, especially if the evil is in some kind of software, trained security professionals are the best to determine the breadth of the problem. This is also the point when a criminal case can start being built, and you really want people who are trained in handling evidence to be doing this analysis.
But, really, how far do you have to go? For routine admin departures where expectation of evil is very slight, the full circus is probably not required; changing admin-level passwords and re-keying any external-facing SSH hosts is probably sufficient. Again, corporate security posture determines this.
For admins who were terminated for cause, or evil cropped up after their otherwise normal departure, the circus becomes more needed. The worst-case scenario is a paranoid BOFH-type who has been notified that their position will be made redundant in 2 weeks, as that gives them plenty of time to get ready; in circumstances like these Kyle's idea of a generous severance package can mitigate all kind of problems. Even paranoids can forgive a lot of sins after a check containing 4 months pay arrives. That check will probably cost less than the cost of the security consultants needed to ferret out their evil.
But ultimately, how deep you have to dig is determined by:
The expectation that evil was done
The expected skill level of any evil being done
The systems potentially exposed to the evil
The potential damage of any evil
Regulatory requirements for reporting perpetrated evil vs preemptively found evil. Generally you have to report the former, but not the later.
But ultimately, it comes down to the cost of determining if evil was done versus the potential cost of any evil actually being done.