Yes, the query will start to get slow quite quickly as the books increase - MySQL isn't particularly good at joining a table to itself (which is what the aliasing solution does).
What may be better is for you to pass most of the 'processing' or 'matching' logic over to PHP, and just use MySQL to get the basic information. For example, you could probably get similar results through two, quick Selects. Firstly, you could select the id numbers of all the people in a certain state:
SELECT DISTINCT id FROM table1 WHERE state = 'virginia'
Then, get a list of fk_ids from table 2 that have rented out any of the books, e.g.
SELECT fk_id FROM table2 WHERE book_name IN ('Harry Potter', 'Gone with the wind', 'any other book title', 'etc')
You could then use PHP to:
find out how many times each fk_id appears in the second set of results. If an fk_id appears the same number of times as the number of books, then that person has read all the specified books.
You can then 'filter' or 'narrow down' this list by checking these people against the ids you have in the first set of results. If they are also in these results, they match all of the requirements (i.e. they have read all the books and live in the correct state).
Is that a valid solution, or do you need a more heavily MySQL-based answer?