Removing Internet records

I often get asked by staff how to remove all traces of visiting web sites from their PC and Internet Explorer. The machines go around a proxy server, not through it, but we need to be able to ensure that all traces of sites visited, images, info etc is completely removed.

I have tried a few programs that claim to remove the files but they report no files are saved so that has to be wrong because we tested it by surfing for a while, running the program, and still nothing.

What steps are the most effective for ensuring the PCs have no evidence of where people surf?

And would a LAN Unix or NT server or a proxy server that PCs don’t go thru be able to save addresses of sites we have visited.

Thanks
Network Assistance Section