This is, I believe, the key question on which the quantum theory of gravity and our understanding of cosmology, depends. We have made tremendous progress in the last years towards each goal, and we come to the point where we need a new answer to this question to proceed further. The basic reason for this problem is that most notions of time, change and dynamics which physics, and science more generally, have used are background dependent. This means that they define time and change in terms of fixed points of reference which are outside the system under study and do not themselves change or evolve. These external points of reference include usually the observer and clocks used to measure time. They constitute a fixed background against which time and change are defined. Other aspects of nature usually assumed to be part of the background are the properties of space, such as its dimensionality and geometry.
General relativity taught us that time and space are parts of the dynamical system of the world, that do themselves change and evolve in time. Furthermore, in cosmology we are interested in the study of a system that by definition contains everything that exists, including all possible observers. However, in quantum theory, observers seem to play a special role, which only makes sense if they are outside the system. Thus, to discover the right quantum theory of gravity and cosmology we must find a new way to formulate quantum theory, as well as the notions of time and change, to apply to a system with no fixed background, which contains all its possible observers. Such a theory is called background independent.
The transition from background dependent theories to background independent ones is a basic theme of contemporary science. Related to it is the change from describing things in terms of absolute properties intrinsic to a given elementary particle, to describing things in terms of relational properties, which define and describe any part of the universe only through its relationships to the rest.
In loop quantum gravity we have succeeded in constructing a background independent quantum theory of space and time. But we have not yet understood completely how to put the observer inside the universe. String theory, while it solves some problems, has not helped here, as it is so far a purely background dependent theory. Indeed string theory is unable to describe closed universes with a positive cosmological constant, such as observations now favor.
Among the ideas which are now in play which address this issue are Julian Barbour's proposal that time does not exist, Fotini Markopoulou's proposal to replace the single quantum theory relevant for observing a system from the outside with a whole family of quantum theories, each a description of what an observer might see from a particular event in the history of the universe and 't Hooft's and Susskind's holographic principle. This last idea says that physics cannot describe precisely what is happening inside a region of space, instead we can only talk about information passing through the boundary of the region. I believe these are relevant, but none go far enough and that we need a radical reformulation of our ideas of time and change.
As the philosopher Peirce said over a century ago, it is fundamentally irrational to believe in laws of nature that are absolute and unchanging, and have themselves no origin or explanation. This is an even more pressing issue now, because we have strong evidence that the universe, or at least the part in which we live, came into existence just a few billion years ago. Were the laws of nature waiting around eternally for a universe to be created to which they could apply? To resolve this problem we need an evolutionary notion of law itself, where the laws themselves evolve as the universe does. This was the motivation for the cosmological natural selection idea that Martin Rees is so kind to mention. That is, as Peirce understood, the notions of evolution and self-organization must apply not just to living things in the universe, but the structure of the universe and the laws themselves.