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. But first, a tl;dr
If you only want to watch anime:
- Watch Ufotable's version of Unlimited Blade Works (prologue, first half, second half [to air April 2015])
- Wait for Ufotable's version of Heaven's Feel
- Then, watch the Fate/Zero anime (first half, second half)
If you're willing to do whatever:
- Read the Fate/stay night visual novel
- (Optionally, watch the Ufotable versions of Unlimited Blade Works and Heaven's Feel)
- Watch the F/Z anime.
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 by DEEN adapted a highly condensed form of the the Unlimited Blade Works route.
- Fall 2014 and Spring 2015 saw another adaptation of Fate/stay night, this time by Ufotable, which adapts the Unlimited Blade Works route.
- At some point in the future, Ufotable will release a movie or series of movies that will adapt Heaven's Feel
- There is also a manga series that (I believe) adapts the Fate route, but I'm going to ignore it, because it's generally thought 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 pretty good, but if you want to read it, I recommend that you do so after watching the Fate/Zero anime.
- It was adapted into a 2-cour anime by Ufotable in Fall 2011 and Spring 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 option is:
- Watch Ufotable's version of Unlimited Blade Works. Then, once Ufotable's version of Heaven's Feel comes out, watch that. Finally, watch the F/Z anime.
The next-best option is:
- Watch the F/Z anime. Then, watch Ufotable's version of Unlimited Blade Works. When Ufotable's version of Heaven's Feel comes out, watch that, too.
There are pros and cons to watching F/Z first vs. watching F/sn first. Each one spoils material for the other. On the whole, though, I feel that watching F/sn first is the correct choice, since this is the "production order" of the series - the F/sn visual novel followed by the F/Z light novels.
For incredibly spoilery details on how they spoil each other, see below:
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.
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. If you really want to know what happens in the Fate route, I guess you could watch it, but honestly, lots of what happens in Fate is also referenced in UBW and Heaven's Feel, so you'll be able to piece it together after watching the Ufotable version of those two routes.
I also do not advise watching the UBW movie at all - Ufotable's version of Unlimited Blade Works is strictly better in every way that I can think of (animation, pacing, etc.).
But you already watched the DEEN F/sn anime
Well, in that case, you're sort of in an "ideal" position - now you can watch Ufotable's version of UBW and (when it comes out) Heaven's Feel, and at the very end, Fate/Zero. This best emulates the "production order" of the Fate series without having to go to the visual novel.
You are open to anything
You have one clear-best option.
Read the F/sn visual novel. Then, watch the F/z anime. Optionally ― if you can grok Japanese or tolerate fan-translated light novels ― read the F/Z light novels.
At any time after reading the UBW route, watch Ufotable's version of UBW; at any time after reading the Heaven's Feel route, watch Ufotable's version of Heaven's Feel (assuming it has come out). The Ufotable version of UBW has a few extra scenes, and is generally agreed to be a very good adaptation of the visual novel (given the constraints of anime as a medium). So, if you want to see your favorite fight scenes animated, or just want to hear more lines by your waifu, I'd say go ahead and watch it.
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 in 2005). You can read this at any time after finishing the F/sn visual novel. It will probably be rather confusing if you've only watched the Ufotable versions of UBW and Heaven's Feel, since they do omit a fair bit of detail that is important to getting the jokes in Fate/hollow ataraxia.
If you can't read Japanese, this may be an unpleasant experience. The English translation patch is... not great.
Fate/kaleid liner Prisma Illya
Fate/kaleid liner Prisma Illya is a spinoff manga (parts one, two, three) that shares characters and universe concepts with F/sn and F/Z but is otherwise rather dissimilar. A 10-episode anime season aired in summer 2013 and another 10-episode season ("2wei") aired in summer 2014. A third season ("2wei Herz") is scheduled for summer 2015.
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.
There are also a lot of spinoffs. To name a few, Fate/apocrypha, Fate/Grand Order, Fate/strange fake, Fate/Extra, Fate/Extra CCC, Fate/Unlimited Codes, Fate/tiger colosseum, and Fate/Prototype. You can probably read/play any of these after reading the Fate/stay night visual novel or watching the 2006 DEEN anime or Ufotable UBW or Ufotable Heaven's Feel. None of them are particularly "important", but you may find them fun.
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. Read them if you like, or don't. Whichever.