Just clearing the browser history does little. There are still traces of your web wanderings all over the system, so it is hard to guess what specific method he may be using. There may even be software installed that tracks where you have been. If you are hooked to a router, there may be records stored there. There is all sorts of free software available with the ability to find visited urls. Sorry I can't be more optimistic.
THere are some web sites that allow one to surf anonymously, that is, you surf the web through one of their web pages, so all that should show up in your history is a record of visiting that site. You might try the free services on this site (the free service is very slow):http://www.anonymizer.com/
I am not sure what traces it leaves behind, but if he is still able to get the urls of sites you visited, I would suspect a keylogger. If he can't, then he is pulling the information from any number of other places on your computer. For instance, if you have an anti-virus application with a built in firewall, then it will keep track of sites visited also.
Edit: It turns out that the URL I gave you does not seem to have an online component anymore..or at least I couldn't find it. This site may be much simpler:http://proxify.com/
It is pretty zippy.