Thanks to everyone for all their help. Everyone gets a ++, but extremely gets the gold star! It was his comment about double-quoting that let me to a solution to my problem. Turns out that quoting it twice won't do it, because that doubles the surrounding quotes too. But I got the following to work:

$bar=~s/'/''/g;
$dbh->do('exec sp_MyStoredProg @foo=' . $dbh->quote($bar));
[download]

which effectively turns something like can't into 'can''''t', which is just what the stored proc needs.

Thanks again to everyone!