If you ask five people this question, you'll get six answers. There are conflicting opinions on this, and I'll try to outline the major options available in this answer. For a tl;dr, see the bottom of this answer.
It is generally agreed that Fate/stay night and Fate/Zero are the two core works of the Fate series. They both come in multiple forms. Whatever you do, consuming these two works in some form is the first thing you should do.
- Fate/stay night was originally a 2004 visual novel that had three routes - Fate, Unlimited Blade Works, and Heaven's Feel (in that order).
- The 2006 anime by DEEN mostly adapted the Fate route.
- The 2010 movie version of Unlimited Blade Works adapted (as you would expect) the Unlimited Blade Works route.
- This fall (i.e. fall 2014) will see another adaptation of Fate/stay night, this time by Ufotable. As of this writing, we don't know which routes it will adapt.
- There is also a manga series that (I believe) adapts the Fate route, but I'm going to ignore it, because it's generally agreed to not be that great.
Fate/Zero is a prequel to Fate/stay night.
- It was originally a light novel series (2007). Fate/Zero has no concept of routes, so all media of Fate/Zero cover the same material, more or less.
- It had a manga adaptation (started in 2011; ongoing)
- It was adapted into a 2-cour anime by Ufotable in 2011-2012.
Below, I discuss some possible scenarios for consuming F/sn and F/Z.
You want to stick to watching anime
In this case, the best options are:
- Wait for the Ufotable F/sn anime to air. Watch that, and then watch the F/Z anime.
- Watch the F/Z anime. Then, when the Ufotable F/sn anime airs, watch that.
There are pros and cons to watching F/Z first vs. watching F/sn first. Each one spoils material for the other. In particular,
If you watch F/Z first, you know how messed up the Matou family is; you know that the Grail is corrupt; you know about Kiritsugu's affiliation with the Einzberns; you know that Sakura and Rin are sisters; you know that Kotomine is not a good guy. These are all major reveals in Fate and Heaven's Feel, and I think that knowing these things in advance impedes one's enjoyment of those routes.
On the other hand, if you watch F/sn first, you know how the Fourth Grail War ends - but this isn't a bad thing. That's how all the original readers of Fate/Zero went into it, and Urobuchi Gen wrote the light novels with that in mind - the dramatic irony that we know that everything's going to hell in a handbasket but they don't is what gives F/Z a lot of its impact.
The above is mostly a matter of opinion, but I think that the fact that F/sn was first produced before F/Z suggests that it is the way to go.
All things considered, it is difficult for me to make a recommendation at this point, since the Ufotable F/sn anime hasn't come out yet, but odds are that when it does, I will favor option (1) for the reasons outlined in the spoiler block.
I do not advise watching the DEEN F/sn anime (the TV series) it is poorly produced, both in terms of objective quality (art, animation, etc.) and in terms of faithful adaptation of the original work.
I also do not advise watching the UBW movie unless you have already read the UBW route of the visual novel - anime-only fans of F/sn will be utterly baffled by the movie. It has a bunch of cool fights, but the plot is a complete mess. It basically functions as fanservice for people who already read the UBW route of the visual novel.
But you already watched the DEEN F/sn anime
Well, in that case, you've already been spoiled for quite a few things, so you may as well go ahead and watch the F/Z anime and then catch the Ufotable F/sn anime when it comes out. (OP, this is for you.)
You are open to anything
You have one clear-best option.
Read the F/sn visual novel. Then, watch the F/z anime. Then ― if you can grok Japanese or tolerate translated light novels ― read the F/Z light novels. At any time after reading the UBW route of the F/sn visual novel, you can watch the DEEN UBW movie (for animated fight scenes).
I will revise this answer once the Ufotable F/sn anime is complete - it is likely that tossing it into the mix at some point will be a good idea.
What about all the other Fate/asdfghjkl stuff?
In this section, I've mentioned the major Fate/ works that people often have questions about; if you have any other questions, leave a comment and I'll update.
Fate/hollow ataraxia is the sequel visual novel to F/sn (released 2005).
You can read this at any time after finishing the F/sn visual novel. If you can't read Japanese, this may be an unpleasant experience.
Fate/kaleid liner Prisma Illya
Fate/kaleid liner Prisma Illya is a spinoff manga that shares characters and universe concepts with F/sn and F/Z but is otherwise rather dissimilar. A 10-episode anime season aired in 2013 and another 10-episode season is airing now (summer 2014)
You can watch or read this at any time after finishing the F/sn visual novel or F/Z in any form. You will get more of the jokes if you've finished both and also gone through Fate/hollow ataraxia (the sequel visual novel to Fate/stay night).
The rest of the Nasuverse
The Fate/ series shares a universe with a number of other works by Nasu Kinoko (the author of F/sn), including Tsukihime, Kara no Kyoukai, and Mahoutsukai no Yoru. Some of these are dependent on one another, but they're all essentially wholly decoupled from the Fate/ series, so you don't need to worry about them for the purposes of watching the Fate/ serie.
If you only want to watch anime, wait for Ufotable's F/sn adaptation this fall, watch that, and then watch the F/Z anime.
If you're willing to do whatever, read the F/sn visual novel, watch the UBW movie, and then watch the F/Z anime.