As @Khaled said, giving root away is impossible to track if the user is out-and-out hostile but for an identified user, of unknown quantity, its better to treat them like a naughty child. There are some steps, below becoming progressively more paranoid with each one... ;-)
1) Inform them that you are watching.
Set a suitable login policy message in /etc/motd for example;
------------------------------------------------------------------------
This is a private system; explicit authorization from the system owner
is required for access or use. Unauthorized access or use may result
in severe civil and/or criminal liability, including without
limitation under 18 USC Sections 1030 et seq. All rights whatsoever
are reserved. All activity is monitored and logged.
------------------------------------------------------------------------
2) Make sure that they are aware that there are rules.
Use sudo rather than root to provide administrator privileges.
A full sudo user has the same permissions as root, and hence can cover their tracks. But it is difficult, and would require a sophisticated used to erase their deeds, and erase the entries from the /var/log/auth.log
3) Have records that cannot be tampered with.
Use centralized logging and ship instance logs for /var/log/auth.log and for /var/log/messages kernel messages.
A centralized log server cannot be tampered with by the remote root user, unlike the local syslog, and the kernel and its modules. rsyslog, syslog-ng, logstash and other provide centralized logging solutions
4) Know what has been changed, by whom, when and for what purpose.
audit local activity using auditd and a basic ruleset. Or deploy AIDE or some file checksumming database.
auditd is a system daemon that records system events to a log-file,
There are a bunch of tutorials here...
http://doc.opensuse.org/products/draft/SLES/SLES-security_sd_draft/cha.audit.comp.html
http://doc.opensuse.org/products/draft/SLES/SLES-security_sd_draft/cha.audit.setup.html
http://is.gd/34J33G
http://www.ibm.com/developerworks/linux/library/l-security-audit/index.html