How can I clear gedit text search / replace history?

Start gconf-editor:

gconf-editor

Go to /apps/gnome-settings/gedit/history-gedit2_search_for_entry and /apps/gnome-settings/gedit/history-gedit2_replace_entry_with and remove the content there: