Create global fields for the fields you want to search. Go to a layout with the global fields. Have the user complete the fields. Switch tot he Find Mode and search using the global fields. If you get an error message for NOT FOUND, then add a blank record. Fill the records with the global field data.
For examples of the scripted find that TKnTexas is describing, see: Scripted Find Examples
It would also be possible to use a script with Modify Find to return to find mode with the criteria still in the various fields, then you could use set variable to copy the data out of these fields into variables. Then your script could return to browse mode and in a very similar fashion, create a new record and copy the data from the variables into the fields of the new record with a series of set field steps.