The questions' probably similar in nature to another one that could be asked, namely how does a calculator know the answers to every sum there is? Of course no-one went through telling it 1+1=2, 1+2=3 and so on, but gave the calculator a general method that it could apply to answer any sum it was asked. While the methods in Google search are undoubtedly more complicated, the idea is the same: the methods are general and can applied to an arbitrary search string even if it's never been tried on Google before.