I can remember many many moons ago I got hacked too so I know the feeling. If you don't have mission critical stuff, this can be a good thing though, makes you learn how to lock down your servers.
Besides locking down your SSH config, Fail2Ban is nice, and be sure to set your iptables so your only accepting packets you want. Also here's a list of other things I usually do:
1. Depending on your distro there's usually a way to install automatic security updates, in debian its called unattended upgrades (https://wiki.debian.org/UnattendedUpgrades)
2. Install logwatch to keep yourself periodically updated with whats going on.
3. Control your packages. If you don't need services make sure your box is clean of them. Basically, for every service you have on the machine thats one more possible attack point, so just use the ones you know you need.
4. In your firewall ignore icmp_echo and icmp_echo_ignore_broadcasts if you can. There's also other stuff you can do in sysctl and with SELinux but I've never really had the need.
I know sysadmins that love to disable ICMP, hence why I consider it a terrible way to test or benchmark anything, but why do you think it should be disabled?
When I scan a network or a host my muscle memory types -P0 just after nmap, so I thought ignoring pings was more a hassle than a security advantage these days... But I might be wrong :)
I blogged about it and posted on reddit. Lot's of people gave me useful feedback (checkout this link http://www.reddit.com/r/programming/comments/1vo7zv/kids_thi...)
I'd recommend (as others have said here) disabling password login via SSH (only keys), disable root login, installing fail2ban, update the system regularly, setup firewall to close ports that don't need to be open.
Out of the box a fresh ubuntu server is pretty secure so you had to install something that exposed some type exploitable code and that's how they got access to your machine.
Anyway, before reinstalling you should definitely quarantine your box and figure out how they got in before reinstalling. Because if and when you don't know, and the specific vulnerability is inside the current version of your Linux distro the chance is almost 100% they will discover a fresh target once they scan for vulnerable servers and they will hack your box again.
How do you know it got hacked?
Here is a good read about basic security: http://plusbryan.com/my-first-5-minutes-on-a-server-or-essen...
