It is very important to note that using brute force is NOT the answer! Initially, I tried to use just some pliers at the points where the green arrows are (photo in step 3), and NOTHING happened! After thinking about it overnight however, I employed the technique I have described here (using just my fingers) - the link almost fell apart in my hands! No pliers or force required.
The Powerlink is two pieces, each being a combination of a outer plate and a pin. The pins latch into the hole in the opposite half of the Powerlink. Alright, you know all that. The part that you may not be aware of is that the pins have a bit of a "head" on them that sit in an inset in the other plate. This makes it impossible to release the link when the plates are out all the way. They have to be pressed inward ever so slightly to get the head out of the inset. Take a look at the photos.
Step 1: Get Some Slack
Before you can get the Powerlink to release, you will need to get slack in the chain so you can work with it. You probably knew this, too. Just in case you didn't, the standard way of getting slack is to put the chain on the smallest sprocket on the rear and also the smallest chainring on the front. Then you pull the chain off the front chainrings altogether so that it's hanging on the frame. If, like many of us, you intend to clean the front chainrings, this would be a good time to remove them since that will allow you pull the chain behind the bottom bracket (that thing the chainring and pedals mount on), getting even more slack. The idea is to get enough slack so that you can isolate the Powerlink as shown in the photos.
Step 2: Clean the Powerlink
You want to be able to squeeze the Powerlink plates together a bit, which means you have to eliminate all the dirt that you can. I like to use penetrating oil for this. The various brands include LiquidWrench, LPS, and of course, WD-40. You could also use some degreaser or carburetor cleaner. An old toothbrush in combination with the cleaning solution works really well.