Is the other guy on to you? If he has physical access or root access, he can erase all his traces and even plant a bug to spy on you. On the other hand, some traces are a pain to erase, and it's hard to think of everything.
Various things are already recorded in the system logs, typically in
/var/log (some systems use a different location such as
/var/adm). Under a normal configuration, all logins and mounts are recorded, amongst others. If you're worried about logs being erased, you can set up remote logging (how to do this depends on the syslog implementation, but it's generally one or two lines to change in a configuration file on the sender and on the receiver).
If you or your distribution hasn't disabled this feature, every file has an access time (“atime”) which is updated whenever the file is read. (If the filesystem is mounted with the
relatime option, the atime is not updated.) The atime can be faked with
touch -a, but this updates the ctime, so it leaves a trace. (Even root cannot directly remove this trace, you need to bypass the filesystem code.)
Various programs have a session history. It's easy to remove or fake, if the intruder remembered to do so. Bash keeps
~/.bash_history, browsers tend to write lots of stuff in their profile directory, and so on. You may also find telling errors or warnings in
/var/log/Xorg.0.log or other system-dependent location.
Many unices have a process accounting¹ feature. See for example the GNU accounting utilities manual, the entry in the FreeBSD handbook or the Linux howto or the Solaris guide. Once enabled, it records what user launched what process when (it logs
execve calls), and perhaps a little more. There's a lot of interesting information it doesn't log, such as the files accessed by the process.
If you want to monitor all accesses to a filesystem, you can provide it through loggedfs. It's very easy to notice if the guy thinks to look.
There are more comprehensive logging programs, but they might require additional kernel support. On Solaris, FreeBSD, NetBSD and Mac OS X, there is dtrace (there's a Linux port in progress but I don't know if it's reached a usable stage). You can also trace specific processes through an interface to the
ptrace system call, for example
strace on Linux; it may induce a noticeable slowdown.
¹ Something that's not in Wikipedia? Nah, that's crazy talk.