Pagination is a hack. Infinite scrolling has its issues-- in particular when the scroll bar changes to a new 100% setting as you use it-- but that is still much better than the click, click, click experience of paging. Best would be to calculate how many results total on page load, and set the scroll bar to match the length of those results, then load the results on the fly as needed.
Pagination is a work-around for the fact that it is not always feasible to send all results in the first view, which would typically make for an ideal user experience.
dhmholley is right that users want relevance, so focus on that above all else. Scrolling is also a hack, to make up for the fact that we don't have screens the size of buildings or eyes that can read infinitely small text. So the overarching goal is to get the best, most relevant results to users in the first screenload of results.
That said, the concept of "milestones" or waypoints within a very long scrolling result is enormously valuable. For example, if I have infinite scrolling, how can I find that one screen with the two things I thought were right? If a long result set breaks results into numbered "chunks", then this aids the user having reference points to return back to.
For example:
--- MYSEARCHCRITERIA : Page 1 ---
result1
result2
result3
--- MYSEARCHCRITERIA : Page 2 ---
result4
result5
result5
--- MYSEARCHCRITERIA : Page 3 ---
... you get the concept. Breaking the continuous result into numbered chunks is still helpful even in a list that is not actually separated into pages.
Oh and don't forget to reflect back to users what it is they searched on!