Haven't rebooted Ubuntu server in 4-months with updates. This okay?
 

I'm usually familiar with the Windows world of doing updates and then having to reboot the machine for the updates to take effect. Is this the same case with Linux servers? I can understand if it's a new kernel, but I'm getting updates to things like DNS, SSH, SAMBA, some library files, tar, etc... I see that for some of the services the system stops and restarts the service, so I'm assuming the new updates are in effect? My users are running files on the server 24/7 so I can't really reboot it without giving them waaaay advanced notice, and usually they are finicky about that since they hate to have their jobs interrupted.

There is no need to reboot a Unix server unless you have updated/changed the kernel (and there are even ways to avoid that by booting another kernel from inside of the running one). Once you have installed the updates, the daemons should either restart themselves, or at the very least will be running the new version once the next request comes in from the client side (depending on which service we are talking about).

What if the update has no service associated with it? For example, TAR. It will just replace the TAR binary and associated files and the next time I run TAR it will be the new and updated version?

Yes, yes it will.