What's the good practice of retriving data from a table with millions of data?

During an interview, an interviewer was asking this question and I didn't answer well. The question is: if we have a table which has millions of records. Each record has first name, last name and telephone number. On the web page, we have three textboxes: FirstName, LastName and Telephone and a Search button. If users click on the search button, it will retrieve data from the database and display 20 records on each page. What's the good practice of retrieving the data? Should we get all matched data and put them in a buffer? or we get the first 20 records only? If users click on "Go to next page", then we retrieve the next 20 records from the database. How should we right a stored procedure for this process?