A counter is a Pokemon who completely shuts down said threath. An example of this is Gligar and Heracross. Gligar counters any and all variants of Heracross, who can at best hope to deal minor damage to it. At the same time Gligar can cause tones of hassle for Heracross, making it a great counter to it.
Counters are usually wall's who is perticulary good at dealing with certain or many threaths. Skarmory is a terrific counter to most physical Pokemon, but counters very few specific Pokemon. Jellicent on the other hand is a good wall, not great, but good. However, it counters Keldeo extremely well, shutting it down almost completely.
So all in all, a counter completely stops opposing Pokemon, or prove a major hinderance towards them.
A check on the other hand is merely able to kill the threath, not take a hit from it. Lets use Flygon and Palkia as an example. They have the same Speed, and both have enough Power to kill each other of. None can saely take a hit from each other, but both can safely kill each others. Thus they check each other.
Checks are usually more of a sweepy nature, who can retaliate against a major threath but maybe cant propery take a hit.
If we look at Heracross again, Tornadus is a check to it, seeing as Tornadus can OHKO Hera withouth issue, but can still be OHKO in return.