To determine what software has been installed, you can review /var/log/dpkg.log
However, this may not be a complete record. There may be binaries and code that was compiled manually or copied directly to the system pre-compiled.
You could compare a default install of the same Ubuntu version and type to the server(s) and look for what files are different, but that can be quiet tedious. A file monitor solution would be ideal (tripewire, inotifywatch, etc.)
http://linuxcommando.blogspot.com/2008/08/how-to-show-apt-log-history.html
You need to check EVERYTHING on the server. Every user account in /etc/passwd, every application user account (such as users in Apache/PHP, database accounts, etc.) should be accounted for, and you should change all the passwords.
You should check to see what services are launched on boot, what the default runlevel is and what starts with it and with other runlevels.
I would use a vulnerability scanner and a baseline configuration tool to audit the current state. The Center for Internet Security offers a free configuration assessment tool, but it may be limited. They have more advanced tools for member organizations ($).
http://benchmarks.cisecurity.org/
OpenVAS is a FOSS scanner, not unlike Nessus, which may have similar capabilities.
There are many, many more things to check, but this answer is already getting a bit long... (Code review for webapps and web pages is a good example.)
You can see review the state of ports available for connections to the servers with a variety of flags for netstat.
http://www.thegeekstuff.com/2010/03/netstat-command-examples/
To identify who has been connecting to the server you will have to resort to the sexiest of Internet Security activities, reviewing system logs. The info can be in any one of a number of logs depending on what applications and servers are on the system. You may also have some luck with external network logs, if they exist.
You have a lot of follow up to do. You indicated that the previous admin was fired; if you suspect malicious intent from that person (i.e. they may have left backdoors, boobie traps, logic bombs, etc.) your almost certain to be better off rebuilding the servers from clean media and reimplement the webapps on them. If this previous admin had full access and control to those system and was not subjected to diligent auditing and overwatch, you should probably assume there are backdoors.
This is based on a pessimistic assumption about the previous admin. Unfortunately that is the way the cookie crumbles for operational network security. There is a lot more to consider, as I said...way more than can be covered here. These points should give you some things to start doing so you can report to management that you are making some progress; but to be brutally honest, if you are not a security professional and you have reason to suspect this person did act with malice, you are probably in over your head.
It is an unpopular answer with management because it requires a lot of effort (which means more $), but the general security minded answer is when in doubt, wipe and rebuild from clean sources. That is how most important gov't systems work with malware; if an alert comes up from AV, the system is segregated, wiped, and rebuilt. Hope you made a backup cuz that data is GONE.
Good luck, and I hope this was helpful and not just depressing.
