I looked at all recently modified files and ran tripwire but could find very little changes. I believe that a directory was created ("/usr/lol" I think) and /etc/motd was changed. Also, ports were open that I don't recall being open before: 6711 and 31965. I don't know what services use these ports.
It's very common for a box that's been broken into to run some service on a non-standard port, to allow login to the intruder, preferably without showing up in records used by w(1) and last(1), or logging via syslog. The other obvious reason for ports being open is if connections have been made to other machines. A client of a service, will connect to the well known port eg) ftp, ftp-data, ssh, smtp etc, but the source port is chosen by the client OS. They are also likely to use your machine as a login redirector, to attack somewhere else, and have it look like it is coming from your network. Another fun one, is to set up a DoS attack against some other site, where your machine is used with an army of others to swamp machines and internet connections of the victim.
I am a Linux security novice and would appreciate feedback regarding 1) how this attack may have been accomplished and
This depends on what packages and what versions you run on your machine. There have been a number of security patches to the linux-kernel, 2.2.16 and 2.2.19 fixed issues for example.
2) what I should do to secure this box. I am working on configuring a firewall script but am afraid I might miss some security flaws created by the attackers.
You need to take it off line, preferably do a clean room OS install, you could verify rpm's against original installation from CD-ROM, and packages from download, search for setuid scripts etc. You'll probably find programs like /bin/login have been tampered with. However now your network has been penetrated, I'm afraid you cannot make the assumption that only this machine has been 'rooted'. You really need to make an emergency damage assessment and recovery plan, involving disconnection from the net, and installing clean version of OS with all security patches (use SuSE 7.1 or 7.2 if you can get your hands on it). Good luck Rob