The pre-quantum universe of Newton is deterministic. In principle, if at some particular instant, you could determine the locations and speeds of every particle in the universe, then you could use the laws of physics to predict the entire future of the universe, and its past as well.
The development of quantum mechanics has led to a view of nature which says that certain aspects are not determined before they happen. That is, you can't predict certain outcomes of physical processes with certainty before they happen.
Einstein was not a big fan of quantum mechanics. He hoped that somehow, underneath it all, the universe would turn out to be deterministic after all. Hence his comment.