The simplist is to add a button that takes the window into find mode. Another button (or even the same button with a bit of scripting) can perform the find.
Or you can set up some global fields where the users enter search criteria and you can have a script use that data in the global fields to set up one or more find requests and perform the find. The global fields can be fields in a custom dialog, located somewhere on your layout--such as in the header or inside a popover set up for that purpose.
For examples of how to script this type of set up see this thread:
good suggestion from PMJ as always.
I would go a different route...I would either:
1. alter the permission set to prevent deletion and expose the toolbar
2. overwrite the delete button functionality with a custom menu and expose the tool bar.
Good point. No matter which approach you choose to employ, DO set up their privilege set(s) to prevent deleting records and any other actions that they should not be permitted to do.