Does the future already exist? If so, which one? In the NOVA Fabric of the Cosmos program, Brian Greene explains a theory in which there is no "now", or more specifically, now is relative. He describes an alien riding a bicycle on a far off planet who sees our future now if he bicycles towards us.
If he sees our future now, which one does he see? Does it change depending on what we do in our "now"? If it doesn't, does that mean everything is preordained to happen a certain way?
Or did I completely misunderstand Greene's explanation?
 A: I believe Brian Green is referring to the fact that in special relativity, an observer's definition of "now" depends on their velocity.  Specifically, we can define "now" as the spacelike hyperplane orthogonal to the observer's 4-velocity; this hyperplane will therefore "tilt forward and backward in time" based on the observer's motion.  So, from Earth's point of view, a very far-away alien's "now"-hyperplane could intersect our world-line in our distant future or our distant past, depending on small changes in the alien's velocity, such as bicycling in one direction or another.  This doesn't require the alien to actually move an appreciable distance; it's just about his velocity.
However, just because the alien's "now"-hyperplane intersects our world-line in our future doesn't mean he actually sees our future.  Light still travels at a fixed speed, and he can't receive any signals from Earth until those signals have had time to get from here to there.  No causality paradoxes arise in special relativity as long as information travels no faster than light.
A: The alien doesn't really see our future.
He's still seeing our past, but a more recent past than he did before.
Assuming that the alien is 100 light years away when he starts cycling then he is seeing what happened to us 100 years ago. If he "cycled" fast enough (i.e. at an appreciable percentage of the speed of light) so that he was now only 50 light years away then he would be seeing what happened to us 50 years ago. But in both cases he's seeing something that's already happened to us. Nothing he can do can change this.
There would be problems if he could "instantly" (i.e. faster than the speed of light) return to 100 light years away. Then he would have knowledge of events that will affect him in his future (but not ours). This is one reason given as to why some people say faster than light travel is impossible.
A: Brian Greene is talking about the Block Universe view. This is not Universally accepted. The Universe could be atemporal with no time and some scientists even work on a model that on the Plank Scale, Space and Time go back to being seperate as Newton viewed it. At the end of the day its subject to interpretation on how time really is.
A: As already noted, the assumption that the alien can view our future assumes that our future is strictly classical and already determined by times that move from the infinite past to the infinite future. This is clearly an oversimplification of the real physics. If we assume that our future is not already determined for other observers (eg. since we have free will in QM) then we must figure out how another observer could see us approach a black hole event horizon and take forever to cross it. We could say that this future exists in the cosmos of the alien, but not in our cosmos. That would require either (i) that there is no experiment that the alien observer could do to view our actual future or (ii) that we never approach an horizon. Since (ii) seems too restrictive in general, the alien can only interact with us locally, through shared experience. This is more or less the standard view. 
With the uncertainty of QM and QFT it is impossible for things to be preordained (even if free will is illusory). Thus the true nature of the alien's observations of us involve quantum entanglement and probably other non local features of gravity. 
The idea that NOW does not exist makes no sense when we talk about quantum observers, because every measurement is NOW for the observer. Our cosmic time evolves from the Big Bang to our present. We can write down mathematics with future times, but few people believe that these realities actually exist. When we probe locality in HEP experiments, in a sense we are creating our future one moment at a time. The frontier of our knowledge is the frontier of what exists for us. This is Hegel's philosophy, if you like, which puts the NOW in a special position for an observer. 
