In the Find dialogue, and Find what-field, Notepad++ remembers my last searches.
Where is this information stored? How can it be deleted/altered?
you can find it in:
C:\Users\user id\AppData\Roaming\Notepad++\config.xml file
In FindHistory section.
If you wish to use Npp in "incognito mode", you may use ZIP version, just unpack it anywhere, use it, and then shift-delete entire directory. Everything will be removed, nothing is left in registry or AppData or anywhere else.