Can anyone recommend a good software package for South Park-style (construction paper) animation? I've seen many people do South Park style cartoons online but cannot figure out what they use. Thanks.

There is a Christmas South Park, where the boys do just that- make an animation. Go back and re-watch it for step by step directions... ;)

Seriously though, I doubt they still use the old paper cutouts. Some of that animation is done with Flash these days, like Mucha Lucha. You could always use Photoshop to create various body parts, props, eyes and mouths, etc, on different layers. Save each layer as "smiley mouth", "frown", "eyes open", and move them to where you need it.

Of course, if you reeeeeeally want to do it the "Old School" way, get a camera and stand- digital camera would be best- and start cutting out all of the afore mentioned pieces. Place them in position, and click. Repeat as necessary. If you do this in linear fashion, when you export all the images to your NLE, the story's frames will be in order.

Lots and lots of Jolt Cola will help you through all of those reeeeeeally long nights.

They don't do it that way anymore, they use software. I hadn't thought of Flash - that's a great idea. Or Macromedia Director.

Any other software anyone can recommend to make this easier?

Well Hell! If you know Director, you're in! I used that in College a few years ago, and it is just perfect for this!

They use Alias PowerAnimator
http://www.spscriptorium.com/SPinfo/MakingOfSouthPark.htm#Wired

I did try my hand at making my own personal South Park knock off in After Effects, and it worked fairly well. Needed some tweaking at the end but it worked. I've given up the serious animation bug though.

Now, for quick and dirty animation, I use Vegas, Effects Lab, and Photoshop.

That articles references to them switching from power animator to Maya..