My linux server was hacked. How do I find out how and when it was done?

This is kind of a topic in itself; you can google for linux forensics for more information. Basically you'd have to make an image of your drives for offline analysis first off, then wipe the computer and install from clean slate.

And remember all the incidentals. Anyone using the computer could have had their passwords compromised. Change passwords, keep it offline, etc. until you get it in a "clean room" (isolated VM).

Otherwise it's a lot of checking logs (which can be faked) and checking your applications (php scripts? Databases? Updated for latest fixes? other users giving out passwords?)

There's literally no easy way to answer your question since you'd need to do forensic work on the server and check for holes. You could use some automated tools but keep in mind if the attacker had Root privs you can't trust system binaries anymore, and you can't trust the logs.

As for future attacks, depending on how secure you want to make it, you can start by redirecting your logs to a system that is just used for saving system logs. No other access, to reduce the attack footprint.

You'd also run checksum software on your system like Tripwire to check the integrity of your files.

And of course keep up to date with updates and run scanning software that checks for rootkits.

Again, security isn't a throw-the-switch thing. It can be a specialty in itself too. Layered security can get as tight as checking for hosts/IP's that don't belong on your network, encrypting all access to the system, having daily logs of changes found on your system sent to you, and setting up a honeypot on your network to look for strange activity (why is my server trying to connect to port 25 on the honeypot computer?)

First and foremost if you want to check for activity, get the disk image and reinstall the server software. From scratch. The server's binaries can't be trusted anymore.

EDIT - some other things that occur to me since you're running SSH - install denyhosts. It can be configured so that automated attacks against your system on SSHD will be locked out after X number of tries. It can also be configured to update from other denyhost servers in a "cloud" to share locked out IP's to help minimize automated attacks. You can also move the port it's listening on; many people point out that it's just security through obscurity, but given the number of bots scanning, this cuts down significantly on random attempts to break in.

First, make sure the computer is disconnected from any networks.
Second, make sure you get any important data off the drives before booting the hacked OS again.

Start with checking out the time stamps on the files in question. Often they are accurate.
Cross reference those with the httpd log and the auth log if they weren't wiped. If one other the other was wiped, you can bet that was the means of entry. If they're still in tact, you might be able to glean more information on how they got in from the log.

If they're all wiped, you're pretty screwed. It would likely take more time to figure out what happened than it's worth.

You mentioned those two services were running, was there a good firewall in place to prevent everything else from being accessed? Did you allow SSH on port 22; is your login reasonably easy to guess; did you allow password logins; did you have any sort of real rate limiting for password logins? Did you have any additional software installed with lighttpd; perl; php; cgi; a CMS or similar? Were you running updated version of all the software; do you subscribe to security notifications for all the software you run and carefully evaluate all notifications to see if they apply to software you run/expose to the public?