when the search history is empty, how do you know what sites were visited?

Answer 1

With Internet Explorer you can check all those INDEX.DAT files in the history folder on the harddisk.
There's a free forensic programm you can use to create a table of sites visited:
http://www.foundstone.com/index.htm?subnav=resources/navigation.htm&subcontent=/resources/proddesc/pasco.htm