Just try out some common cases with some common queries. Let's say you can search on the first name or the lastname or both from a user. In that case you can create 3 tests to try them all out using some test data. After that you can also write a test that it will not return anything when you type in a firstname that doesn't exist for example. That's the best and easiest way to go.
After that you might find some edge cases you want to test as well. For example starting the search query with spaces or ending it with spaces. You should in your code trim the spaces away before searching if that is a feature.
If you for example use fuzzy-search you might want to misspell the firstname and still get a result!
For your tests itself I would probably test based on the given test data how many results you got back or for example if you use ajax requests if the json structure that is returned is correct and contains the correct data.