When I search my blog, and then click on "older entries" I arrive at a 404 error page from the host. How can I fix that?
I downloaded the theme you're using and pagination works fine, including on the search page. So just about all I can say is that you've changed something while customizing the theme. Try checking the default search.php against your modified one and see if it throws up any clues.