P-linking, or plinking as I'm just going to type it as, means priority linking. Before I get too far into what that means, lets lay down to very important facts you must know about SF4's engine before continuing.

Thing to know #1:
When you hit mp+hp by itself (no stick movements) the stronger button will come out, in this case, a hp

Thing to know #2:
Pushing a button takes 1 frame. Releasing the same button takes 1 frame. This means that the fastest you can put in the same hp input, is once every other frame.
1st Frame: hp pressed, hp triggered
2nd Frame: hp released, nothing triggered
3rd Frame: hp pressed, hp triggered

To plink you hit the button you WANT to come out, and then you hit the button in lower priority: the button to it's left (yes this does mean you cannot plink lp or lk). You have to hit these two buttons in such a short time apart from each other it really does feel like you're pushing both at the same time.
This is notated as hp~mp, the ~ means you will be hitting both, but really only getting the hp.

SF4 likes to help players out, it will turn near half circles into half circles, it will let you put in super jumps while buffering another move - lots of little "shortcuts". A side effect of this is when you put in hp~mp, two buttons so close to each other, the game goes through this process:

Frame 1: Game sees you hit hp, I guess trigger the hp

Frame 2: (this is when you hit mp) Now the game thinks you really meant to press hp+mp, because who hits 2 buttons one frame apart on purpose? The game then produces a mp+hp command, which if we look back at Thing to Know #1, the hp will come out because it's the bigger button.

If you're in training mode you will know this works because you will see:
(mp) (hp)
(hp)
It will see the hp first (so it's at the bottom of the list, new commands come from the top in Training mode), then it will see the mp+hp, which really is just a hp unless you were trying for an ex Hadouken or something.

What does this all mean?
With this knowledge you are able to put in the same button, in two frames back to back. If you remember from Thing to Know #2, you know this isn't something normally allowed by the game engine - plinking is the only way to input the SAME button two frames in a row.

There are combos that give you only ONE frame in order to time them correctly, and with p-linking you can turn this into 2 chances. If you hit the plink on the link (sounds funny but keep up), then it will hit the button you're looking for twice back to back, which gives you slightly more room to get harder combos off.

Any time you have a link, you can p-link, even super easy combos can be plinked without any issues ever coming up - it's just a different way of making sure you hit your links. Just note: you cannot plink lp or lk, if a combo requires you to get a link with those (as many Sakura combos do), then you just have to toughen up and learn the 1-frame link*.

* There are really dirty tricks you can do by plinking with select/start buttons - but that's really more for technical jokes - nobody ACTUALLY does this.

Sorry, plinking is pretty simple but to understand why it's simple you need to understand a bit of the engine first. If you still don't "get it", don't feel bad - just watch videos until you finally do, it's not a hard concept, just not a very straight forward one either.

http://www.youtube.com/watch?feature=player_embedded&v=acuTIlxcjz0

http://www.eventhubs.com/news/2010/nov/21/ssf4-execution-techniques-tutorial-vesperarcade/
This is Vesper Arcade's tutorial, he does a great job of listing everything described here.