I've seen a lot of guides (and some main sources like LoLCounter) where you can see what champion you need to use to lane against a particular champion. I've also heard a million players say that "I cannot do anything against this player — he's my counter".
Now, how do you know that a champion is another champion's counter? For example, how do you get to the conclusion that Ezreal is bad against Miss Fortune?
Edit: Thanks! I tried to improve this answer with a few more examples. Don't hesitate to give feedback.
Rule #1: Player skills over champion matchup. Don't pick a champion you don't feel confident with, just because it should counter your opponent. (Unless you want to practice, of course.)
Rule #2: Don't blindly trust LoLcounter. Why should you?
Rule #3: Every single patch makes part of LoLcounter outdated. Perhaps you shouldn't trust it at all.
Rule #4: If you want, or need to rely on it, detailed and up-to-date comments and debates are worth infinitely more than votes. Frustrated players who lost their lane can, and will vote regardless of whether they have been countered or not. tl;dr most votes are unreliable.
That being said... There are indeed game mechanics that favor some champions in a given matchup. A few examples:
Ryze can root (W, "Arcane Prison") an opponent before damaging him. Kennen's "woohoo" sprint (E, "Lightning Dash") makes him unable to do anything except moving fast, and that is his main farming tool. Therefore, farming with Lightning Dash in front of Ryze is almost impossible.
Short-ranged champions with no gap-closing abilities, e.g. Udyr or Ryze (yes, he has ranged attacks, but his range is shorter than most AP carries) are weak to kiting. Ashe counters Udyr (he can never reach her) and Cassiopeia counters Ryze (she can harass him with Q forever while never entering his casting range). Among AD carries, Caitlyn counters Vayne for the same reason, even though it is less obvious.
Some champions have silencing abilities. They tend to fare better against casters, who rely on casting spells to deal damage.
Jax can dodge basic attacks during his majorette stance (E, "Counter Strike"). That gives him an edge over champions who mostly rely on basic attacks, e.g. AD carries, Tryndamere, AD Master Yi, etc.
Lee Sin has two abilities revealing stealthed champions (Q, "Sonic Wave", and E, "Tempest"), i.e. he counters Wukong, Akali, etc.
Kennen's and Fiddlesticks' ultimates ("Slicing Maelstorm" and "Crowstorm") are area spells that follow them and deal damage over time around them. Which means they will be wasted if the caster is blown away from the fight. Janna's ultimate ("Monsoon") is perfect for this; she is a famous counter to Kennen and Fiddlesticks in team fights only. Other champions with knock-back abilities: Alistar, Jayce, Gragas, Lee Sin and Tristana.
Katarina's ultimate ("Death Lotus") deals huge damage over 2 seconds around her. However, this is a channeled ability. Any crowd-control ability will stop it. Three out of Blitzcrank's four abilities can interrupt Death Lotus, especially his ultimate ("Static Field"), which is an instant and very safe way to disable Katarina. She cannot hope to land her ultimate in the middle of Blitzcrank's team.
Poppy's passive ability ("Valiant Fighter") reduces by half the damage taken from heavy hits (more than 10% of her current health). It makes her highly resilient to spike damage, such as Veigar's spells. However, she is very weak to damage-over-time spells (which are almost never affected) and true damage (which cannot be mitigated). Teemo, Darius and Olaf counter Poppy in top lane.
Some of Malphite's and Rammus' abilities benefit from armor ("Spiked Shell", "Defensive Ball Curl" and "Ground Slam"). They are more efficient against teams that rely a lot on physical damage. On the other hand, 50% of Galio's magic resistance is added to his AP ("Runic Skin"); therefore, he is better against teams that rely on magic damage.
"Yorick walks into a bar... There is no counter." (This is wrong, yet almost true, but I love this joke. Cho'Gath, Nasus and Trundle may benefit from Yorick's ghouls.)
These are only examples. They might even become outdated someday. However, what truly matters is the understanding of game mechanics that leads to these examples.
Always ask yourself "what makes this champion strong? what would stop it in its tracks?".
Bottom line: be your own LoLcounter.
Well the answer is a bit multi-dimensional. There are a lot of factors to consider when counterpicking and thats what makes lolcounter so valuable.
The most important thing to keep in mind is Mechanics. How do your opponents main strengths work? And how (in theory) you could stop them.
For example you have Kennen or Fiddle with their aoe game changing ultimates. Their main strength is that they walk inside your entire team and melt them. What you'd like is a spell that would push them out of there. Thats why alistar (headbutt) or janna (ultimate) are so good against those champions. But those are not same lane counters.
Let's see a top encounter. Take Jayce for example. What is his main strength? It's that bloody ball of light hitting you without even seeing him. What can counter that? Minions in front of you at all times and they also have to be on a distance because its AOE. So Yorick is the ideal counter because his ghouls wander off away from him and he spams them. So most of the times Jayce throws his blast there is a big possibility that a ghoul will be there to block it.
EDIT: I Agree with Aeronth that being comfortable with the champion you pick is more important than trying to counter the other champion. In the end of the day use lolcounter just to get a few ideas/suggestions or if you're time is running up and you can't think of how to counter a certain champion. We don't need to stress too much that lolcounter might be wrong or outdated. It happens with almost every site out there. You always have to use your brains before picking and I consider it a given when I answer a question.
LoLCounter is based on votes, so it's based on the feeling of the people who vote. Sometimes the feeling can be supported by some skill analysis and some common sense.
For this specific example, I would says that MF can counter some of Ezreal's strengths:
Ezreal is pretty safe for farming with his range and mobility but MF can easily harrass him with Double Up in lane and counter his safe farming and bully him.
MF has more heath and a stacking autoattack steroid and applies healing reduction, which reduces life steal. This all means that in trades she will probably win.
Even if Ezreal blinks away, she can try to catch up with her passive or ult.
