How do I choose brake pads? I use the plain self-centering side-pull cantilever brakes found on 99.9% of road bikes. (Well, it's a road bike. ;) ) I've got alloy rims. Both my current internship location and back home are moderately hilly areas, which force me to "ride" the brakes quite a bit. I "pulse" the brakes a bit in order to reduce heat build up and all that jazz, but it seems I go through the pads themselves quite quickly -- my last rear pads lasted less than half a season, and the ones I replaced them with look to be on their last leg now.

I don't have any issues with braking performance -- I just would like to find something that will last longer.

What should I look for? Am I out of luck (e.g. have to switch to something like a center-pull brake design?)
Frankly, unless you are willing to swap to a disc brake bike, you are out of luck. I assume that you are riding the bike regularly, but I would not expect to get more than 1-2 months out of a rubber or cork road brake pad (Cork is typically only used on carbon fiber rims). Especially in a hilly area. You can extend the life slightly by ensuring your rims are clean and dry, but only by a small percentage. A bike ridden in wet weather can use up a set of rubber brake pads in one ride. 1/2 a season or more is an excellent usable life for this type of pad.

A disc brake pad will last much longer, because the pads are made of sintered metal, like the pads in your car. Average life is 1 to 2 years, with variation in riding style and weather. That requires changing at minimum your wheels and brakes, but most likely would require a new bike. Not something I would consider cost effective solely to save money on brake pads.