Don't take it the wrong way, but if you are the admin of that box with that mission, and you need to ask those questions, you'll probably have a little reading to do.
There's a HOWTO for almost each of your points (except, off the top of my head, I wouldn't have a ready solution to match individual users with network destinations, although I'm sure that 3 minutes on google will find you one).
Once you are online after you understand the linux networking HOWTO, start with the firewall. iptables, nice HOWTO available, that will give you security, satisfy most of your logging needs, and can prevent users from accessing inappropriate material such as
http://www.inappropriate.com .
Get tripwire set up so you can feel a bit safer and then the fun can begin.
Sorry if you wanted more specific answers but all of that is nicely documented.
mlp