Can we observe changes in the fine-structure constant? The fine structure constant is a number of constants rolled into one equation. Brian Cox mentioned in the April edition of Focus magazine that it is possible that the speed of light was once faster, say, in the earlier universe - hence I would conjecture this constant must then have been different.
If any or each of the constants that make up the fine structure constant are said to be changing, then is there anywhere in the universe where we can reliably observe this; and if so, what are the consequences in such a case? What of our known laws of physics in such cases, those that are used so broadly to garner great results in the field of astronomy to this day, do they become questionable or blatantly break down?
For reference, this is an excerpt from the magazine concerning what was said regarding observations of the speed of light:

What the astronomers are seeing in
  their study of the distant gas clouds
  is the last cosmic moments of that
  decline.

He further mentions gravity with hints of possibilities of change:

Others look for variations in big G as
  this could be used to develop a new
  understanding of gravity.

These are fitting statements for the source of them, but seemingly fanciful without further detail.
 A: There are some scientists working on this.  Here is a page with some references.  From a quick reading, it seems that there is some evidence that the fundamental constants might be time-dependent.  From one of the papers:

In modern higher-dimensional extensions of the standard model of particle physics,
  low-energy fundamental constants like the fine structure constant α, the proton-electron
  mass ratio μ = mp / me, etc, are expected to be dynamical quantities that show spatio-temporal evolution.

The paper then goes on to review the (then) current state of knowledge, including observations and laboratory experiments used for finding this out.  Since the paper was published in September 2010, it should be fairly current.
A: To detect changes in gravity and the speed of light over time, the place to look is far, far away. I believe one of the goals of the James Webb Space Telescope is to look for this sort of thing--while we can observe some of the farthest galaxies possible, JWST will be able to do so in greater detail.
A: Another method that has been used to measure the fine structure constant is the Oklo natural nuclear reactor in Gabon. Measurements of the Samarium 149 concentration indicate that $\alpha$ has not changed by more than 50 parts per billion in the last 2 billion years - but the change could be as small as zero.
A: Just to add to the already posted answers, the main efforts to observe variations in the fine structure constant have come through looking at the spectral lines of very different objects. The key is to look at sets of spectral lines. Many atomic transitions are split in to multiple closely spaced lines, and the spacing depends upon the exact value of the fine structure constant. The measured spacing between these lines in some very high redshift object (e.g., a quasar), may then be compared to the expected spacing between those lines if the fine structure constant is the same in the past as it is today. 
Of course, looking at very distant objects is not the only way. Some physicists have focused on trying to observe very minute changes in the fine structure constant over human timescales, and the limits that they have placed on variation are competitive with the sorts of variations that can be observed using astronomical techniques. As of 2012, there have been a few papers claiming variation, as well as multiple astronomical observations and experimental physics results that are consistent with no variation. 
