LOL, no, that shouldn't apply to your situation if you're running a shell server...
Is it possible to make it where each user cannot delete their history, and make it where I can see their history, as superuser, so that I feel a little better about giving shell access to users?
First I'd like to warn you that if you're running a shell server then the scope of your "problem" is much wider than this. For instance you will have set up network and service ACL's, select and chown apps they are allowed to run to a different group and remove world perms from others, de-suid some apps, set restrictions on /home mount flags (dev, suid), sanitise your $ENV settings and on and on. This doesn't really depend on how much you trust or distrust those users, but more on how much of the risks you (won't) take for granted. In the end having a local account is a much more comfortable steppingstone for snooping around the system, cuz you're already in and admins trust local users more than they should.
As far as logging is concerned I'd suggest you patch your kernel with Grsecurity(.net)'s patches. Select as much of the options possible, but at least the stack and /proc protection features, "trusted path execution" (TPE), meaning they can't execute apps outside their $PATH (/lib/ld-linux.so trick won't work) and set the options for those users to have their exec's recorded. In addition you could restrict them to only have Bash for a shell and install Bash like this:
http://www.rootshell.be/~unspawn/packaging/bash.html (this one's my rpm adaptation and repackaging, see original URI for more).
Make sure the user can't edit their .bash_profile (or other startup file) and put a line at the end something like script -a <log_file> ; exit
Shouldn't their shell just be "script -a ~/script.log"? Granted, running script gives much more detailed info, and there is a problem as well. More below.
The second, stopping the user from editing the file, I would have to think about a bit.
Not an optimal solution, and I would only recommend it in conjunction with a Grsecurity-protected kernel, even then anything that adds complexity to the system adds it's own pitfalls... If FS is ext2 or 3, as root you could try setting up a separate logdir:
mount /var -o remount,noexec,nosuid,nodev # Curb some user tricks
mkdir /var/tmp/scriptlog # Root-owned, /var 0700, /var/tmp 1777
chmod 1003 /var/tmp/scriptlog # Root-owned, world exec+writes no reads, or chgrp to main usergroup and chmod accordingly.
log=/var/tmp/scriptlog/${LOGNAME}.script
touch $log; chmod 0700 $log; chown ${LOGNAME}.${LOGNAME} $log
ln -sf ~/script.log $log; chattr +a $log
Since this will be a world-writable dir, you should do a quotacheck and edquota ${LOGNAME} so they're not capable of dossing the log partition.
Don't use your root account to snoop inside the dir: use an unprivileged account. Script logs control seq's as well and they may well fsck up your display. Don't use automatic logparsers to log data from this dir: a neat trick could be one semi-colon away. Also a simple "while [ $RANDOM ]; do logger hello; done" will have you grepping around for *REAL* logdata, so that way of dossing the log partition is still open unless you chmod logger accordingly.
In any case YMMV(VM)
[edit]
Stupid I forgot: you should log to a remote syslog server :-]
[/edit]