If you are on computer "A" and you telnet into computer "B", then when you login to computer "B", the shell there will record what you have done. Nothing on computer "A" will be record what commands were issued in the telnet session (which is what I think you are looking for).

If you have used the values for HISTFILE that I recommended (particularly if you add the date), then on compuer "B", you can see the pseudo terminal, and you can use "last" to determine where the user logged in from. You could then use "last" on computer "A" to see who was logged in at that time and go search through their shell histories.

This isn't perfect.

I suppose perhaps you could use "script" to record all input/output of a user session into a file. It's not really made for this sort of thing; putting it in a .profile may get you into an infinate loop. "script" will fire off a shell and when that shell exists, any input/output from that shell gets recorded in a file (defaults to "transcript", but you can pass an argument to write to some other file). Because script fires off shell, if you put it into a .profile, you could fire off a shell that fires off a shell that fires off a shell... infinite loop.
"script" seems to have the level of logging you want, but how to make it work (and how to force users to use it).

I suppose you could packet sniff, say with tcpdump. In next to no time, you'll have a huge file to pick through. I think this would only be practical if you were to target specific users you are suspicous of, etc.