My son's latest collectible minifigure purchase was missing its legs. Is it possible to get a replacement set of legs?
In short, yes it is possible.
The best place to find replacement parts is Bricklink.com.
You don't mention which minifgure is missing its leg, but for example, here is a link to the 'Hips and Legs with Studded Belt and Safety Pins Pattern' of the Series 4 minifg 'Punk Rocker'.
To find the required part for your minifig, a good starting point would be to look thorough the Collectible Minifigures Catalog Gallery on Bricklink and go from there.
As for cost, it varies greatly on based on rarity and desirability of the part you are looking for.
LEGO will replace a part for free on their website, providing it was missing from purchase. Sadly replacement parts aren't available for Collectible Minifigures, but you can contact them to let them know.
Ensure the Minifigure packet has been fully emptied, it's quite easy to lose parts when you open the packet.