if youve left your cache and cookies history yes they can see where youve been, not sure about your log files of IM conversations unless they use packet sniffing, most IM programs dump that from the buffer when you close the program I believe, I know ICQ and its linux clones do
Of course they can, all aim and most other messengers for that matter dump all the text into a log file that can easilly be viewed by anyone that opens the log file from it's directory commonly found in the programs directory. And your internet history can also be viewed. Just clear your cache, cookies, and history to take care of your internet history. For your messengers find out where the log is and delete it.
Some times even with clearing out you log files and clearing you history you can still be found. Some browsers also have the typed address stored in other places rather than history.
The IM convos might not be stored in the Program Files but rather in the hidden folder under the Doc&Settings area also. That is where alot of the programs tend to store their profile info liek Firefox and IE.
Except for Trillian, your conversation are saved within the messenger client window but you can uncheck that service but by default, I believe it is on. So if you have a convo on tues. you close the messenger windows, on wed. you talk to the same person, you can actually see your past convos even with a time stamp