How does my sys admin know that I haven't rebooted my system?

A quick way to check this remotely can be done using SNMP (provided your SysAdmin has set this up on your network):

admin@yourcompany:~$ snmpwalk -v 2c -c <snmpstring> MachineName sysUpTimeInstance
DISMAN-EVENT-MIB::sysUpTimeInstance = Timeticks: (9461615) 1 day, 2:16:56.15

Most likely, the data would be polled and stored in a network management/monitoring system of some sort (i.e. Nagios or Cacti).

In case anyone is interested in playing around with the snmpwalk command, see the answer here to get a basic SNMP configuration set up on your system.

A simple method will be to check the output of the uptime command, which shows how long you have been running the system without a shutdown/restart.

Sample Output:

saji@geeklap:~$ uptime
12:41:29 up  3:08,  2 users,  load average: 1.06, 0.85, 0.86

It says that my system has been powered on for 3 hours and 8 minutes.

The admin can set up a shell script to either make use of uptime or to use some other method, as detailed in this link. Another method the admin can utilise is to setup an email to be send at system shutdown or restart, the details are available at this link.

@saji89 mentioned the uptime command. I'll go one step lower, and simply posit that the sysadmin has a script somewhere that connects to each computer and does a cat /proc/uptime (or something equivalent). The first field of the output is the time, in seconds, since the system was last rebooted, which is much easier to parse than the output of uptime. For example, my computer gives a first uptime field of 1441218.24 with uptime returning up 16 days, 16:20. 1441218 seconds is 16 days plus 58818 seconds, and 58818 seconds is 16 1/3 hours. 16 days 16 1/3 hours.

When you know the maximum length of time since the system should have been rebooted, this data makes it trivial to check to see if the system has been rebooted since then or not.

It could be done through a monitoring tool such as Nagios, or through a separate script that the sysadmin keeps on his computer (or rather accessible through it, I'd imagine) which connects to each computer in turn or in parallell and prints the time since last reboot in some format. That all depends on how elaborate to make it.

Another way, just for the sake of completeness, is to look at /var/log/wtmp via the last command. Example:

$ last reboot
reboot   system boot  3.2.0-36-generic Thu Jan 24 16:25 - 17:42 (1+01:17)   

wtmp begins Tue Jan  1 06:30:03 2013

This method is a favorite because it also happens to be the perfect mnemonic.

Q: When did the last reboot occur? 
A: Just type 'last reboot'

When a package that requires a reboot has been updated via apt, a file called reboot-required is created into /var/run/. The sysadmin can check for the presence of this file remotely to determine if a reboot is required due to updates.

This ...

to apply some patches

is the key part.

If the admin is any good he probably set up the updates from HIS machine so the PC's do not have to download the same file from the web. If so he can see from his own machine who downloaded the patches.

He then only has to look at the IP addresses of those systems that did load the patches and send and email to those that did not. That email can even be an automatically generated mail. Imagine there are 500 machines. Manually checking each of them is a waste of time if there are several methods where he can do from his own machime.

1 very important reason for doing it this way: an admin needs to have control on what is happening on the systems he needs to maintain. So he should always have a single point of control (ie. his own machine where he has all the tools) where he can see the status of any machine.

There are several valid methods described in the answers. Logging in and checking the uptime would be strange for a large company, but doable for a smaller one. The sysadmin could have been checking via SNMP, but the same "trouble" argument could be used there.

The most likely situations are, as far as I'm concerned:

1. The sysadmin runs some sort of checking-software, probably Nagios, that checks clusters of computer for problems. Something like the NRPE plugin will be used for most systems and can show you uptime (apart from disc, logged in users, etc).
2. A similar method can be used to check what is running where. If the to-be-updated-patches can be checked (what kernel are you using), the "are all users updated" script will be still pointing at your computer for being in a 'bad' state.

If the system is connected to a network he controls, the sysadmin can simply look at the switch or the dhcp server to see how long your network connection has been active. That will also tell him you have not rebooted.