Uhm.. Browser?
Im Konqueror ginge das z. B. über Settings -> Configure Konqueror -> History Sidebar und da dann auf "Clear History" drücken.. Firefox müssten dir auch die Windowser verraten können. Ich aber nicht, bin fundamentalistischer KDE'ler.
/edit
HA-HAH! Während du noch bootest hab ich schonmal eine Hilfestellung gegeben :P.