Well, assuming they are using IE to browse the web and further assuming they are smart enough to clear cache, clear cookies and clear history, there is one place that they will more than likely not know about as a history logger.
Just use DOS prompt and browse on over to:
C:\WINDOWS\TEMPOR~1\CONTENT.IE5
In that directory will be a file named index.dat that tracks every webpage the browser has been to REGARDLESS if they clear cache and history.
It's a little hidden something that Microsoft has never really explained exactly what they are up to with, but, I keep all the ones clear on any machine I use.
This directory is generally NOT visible from within windows explorer as windows explorer is programmed to ignore that folder and NOT display it to you.
I would further recommend that you edit it with the DOS edit command and not try viewing it in windows.
That file will pretty much tell you where they've been and unless they are PC guru's that really examine the operating system, they won't even know its there.
After you view the file or copy it across the network or something, you can delete it off the PC as it is automatically recreated everytime windows starts up and then you won't have to look through the same data each time you view it.
Have any questions, let me know.
Good luck!