First, let's have the timeline in terms of release and by system, omitting anything not considered directly applicable (in this case, the CD-I games, Link's Crossbow Training, and the Four Swords title on the Gamecube/Gameboy Advance):
Consoles:
NES: The Legend of Zelda, Zelda II: The Adventure of Link
SNES: Link to the Past
N64: Ocarina of Time*, Majora's Mask
Gamecube: The Wind Waker, Twilight Princess**
Wii: Twilight Princess**
Handhelds:
Original Gameboy: Link's Awakening
Gameboy Color: Oracle of Seasons, Oracle of Ages
Gameboy Advance: Minish Cap, Link to the Past (port of SNES title)
DS: Phantom Hourglass, Spirit Tracks
(Hope I'm not forgetting any.)
*Note: There is a remix of Ocarina available on the Gamecube called the Master Quest version, but it is largely the same game and can be skipped.
**Note: The Gamecube version is considered more "true" because Link is left handed. The Wii version is a waggle fest but runs in wide screen, but because most people are right handed, everything in the world was mirrored in order to make Link right handed. This is considered travesty in terms of canon by fans, and so most would tell you to stick to the Gamecube version.
Zelda games aren't inherently tied to each other. Miyamoto (in case you don't know, he's the creator of the Zelda series) has said that there's no solid time line. Yes, certain games take place after others, but otherwise you can play them in any order. The only exception to this rule are the first two Zelda games - The Legend of Zelda and Zelda II: The Adventure of Link - which are sequential.
Otherwise, the explanation is that there are different versions of Link and Zelda and - if I remember correctly - Hyrule as well. Sometimes certain games reference others (Phantom Hourglass on the DS alludes to things from The Wind Waker from the Gamecube), but generally you can play them in any order.
If you wanted to start proper, I'd play the original NES Legend of Zelda. Most would tell you to skip the second game since it changes up the formula a lot (it is more of an action side scroller, where you have to jump pits and so forth), but I personally like it a lot. Still, the first one on the NES is very fun and very well designed. Be warned that it might be considered difficult by today's standards, and might be a bit much for a newcomer to try.
After that, you could either go to Link to the Past from the SNES, or The Ocarina of Time from the N64. Both are magnificent games, and each further refine the original formula set by the first NES game. They are essentially bigger, have better stories, more sidequests, a wider variety of enemies and items and NPCs to meet, etc. I'd suggest LttP before OoT.
Majora's Mask - like The Adventure of Link - travels far from the cannon path of a typical Zelda game. It is technically a direct sequel to Ocarina, but it is heavily reliant on its "gimmick" of having a system where you replay the same three days of game-time over and over (think Groundhog's Day if you've ever seen it). It is still an excellent game, but it garners a very love-or-hate relationship.
Moving onto the Gamecube, we have Wind Waker. As a 3D title, it most closely resembles and hearkens back to the original Legend of Zelda, and Miyamoto has said several times he was inspired by his original game when making it. The graphics have also created a love-or-hate thing, but I think they are spectacular and still look vibrant, colorful, and smooth even today. Highly recommended, especially because of the more old school feeling nature of it presented with more modern rendering tech.
Twilight Princess, again, seems to split the fanbase. For a more pure play of it, take the Gamecube version. Otherwise, the Wii version is fine, but it is a waggle fest. To its credit, it does run in wide screen. It is much more atmospheric than previous titles, and tends to be darker. Nintendo experimented with a few different things, and some people hated it and others liked it. Oh well.
As for the handheld titles, I'm of the opinion that they are all largely very good, but not necessary (which tends to be something more people don't agree with). Link's Awakening seems to garner the most praise over the years, while the Oracle games feel radically different given that they were developed by Flagship/Capcom instead of directly by Nintendo (but in a good way). I can't say much about Minish Cap since I haven't actually played it.
Phantom Hourglass brings on the touchscreen only gameplay, but most have said that they thought the game was charming. It is an easier title, and thus might be a good one to start with for someone who has never tried a Zelda title before. It would also be better to play it before Spirit Tracks, since it will introduce the gameplay of A) touch screen and B) Zelda titles, which are puzzle based during dungeons. Further, it's a good opener, since it feels somewhat old school in look and presentation, just dressed up with the cell shading style that Wind Waker began.
SO, in short:
Must plays from the consoles are: The Legend of Zelda, Link to the Past, Ocarina of Time, Wind Waker, and Twilight Princess. Zelda II and Majora's Mask have their fans but are generally considered "not as good" as the other titles, and you could always play them later. I personally recommend both nearly as highly as their forerunners, but given how isolated they are from the rest of the series, they can be played later on.
Must plays from the handhelds: Link's Awakening and Phantom Hourglass, and then Spirit Tracks upon completing the latter if you dig the touchscreen controls. The Oracle games can be played later on along with Minish Cap.
In terms of difficulty, I'd say that generally the older the game is, the harder it will be. That might help you decide as well.
As to how to play them, running them on their original hardware is best. If you've got a Wii, you can download several of them from the Wii Shop service, or even play a few directly from Gamecube discs. The emulated Virtual Consoles versions are generally superior, as they run in 480p resolution and don't have near as much slow down that a CD game would have (i.e., running Ocarina from the Gamecube disc it was released on has a delay whenever you access your inventory, which is annoying - it's not game breaking or anything, just very annoying). Further, you can play through all of them from the same system in this manner.
If challenge isn't an issue and you have access to old systems OR have a Wii, then I'd start with The Legend of Zelda and go from there. Otherwise, I'd tell newcomers to go to Phantom Hourglass and play it first. You can work back to other titles from it, because it'll be an easier title while still introducing a lot of the mainstays of the game - the boomerang, hitting color switches in dungeons, etc. If you hate touchscreen play, then just pick either the original LoZ, Link to the Past, or Ocarina of Time.
Be warned that the older N64 titles will look "terrible" in the sense that they are blocky due to polygon limitations of that era, while older titles will not have any flashy effects over their pixelized presentations. So if you're the type to favor tons of graphics, you will be disappointed. But you shouldn't be, because the gameplay is sublime and holds up to this day without issue, especially when you consider just how much of a template games like Ocarina serve for modern day adventure projects.
If you have any more questions, feel free to ask.
Hope this helps! Good luck!
