Well, on Blue's Clues as well, the dynamic duo is also shovel and pail, and it is hard to imagine the phrase shovel and bucket. Google reveals that lunchpail gets 36,000 hits while lunchbucket gets 11,000. Also, the scoop on industrial equipment is called a bucket. This suggests that a pail is something smaller than bucket, though I'm sure that for some they are interchangable.
There are some constructions in which you'd use only one or the other. You'd bring a pail to the beach (as Kalleh noted) and you'd dip a bucket into a well. It would sound odd to do it the other way.
I have just a vague sense that if the object were made of metal it would be called a pail, and if it were made of wood it would be a bucket. (Joe's point about an industrial scoop is well taken; I'm only talking about the everyday hand-held bucket/pail.) Do other folks have the same sense?
For me, and I can only speak for standard southern English not involved in specialist occupations, the only word used is 'bucket'. A 'pail' is only known from Jack and Jill, though I suppose it might even today be the correct term for the metal bucket a milkmaid uses.
Checking the American Heritage, it notes that a bucket is actually a measure of dry measure (equal to 2 pecks=17.6 liters!) and that a pail shares its origin with pan and paella. I'm guessing that wordnerd's distinction is a good one suggesting that a bucket/pail distinction was originally one of material (one being wood, the other metal, hence the fact that bucket stands as a measurement term) that inferred size (because the process to make large metal objects was of much more recent vintage than making similar objects out of wood), but the distinction has been mostly lost. There might be a similar distinction between barrel and tank, but that is better preserved because a barrel has some distinctive features and a distinctive manufacturing process that had a named craftsman (cooper)
Joe, it's so good to see you here. Nice to have Japan represented on Wordcraft!
Now that I think of it, Wordnerd's distinction does make sense. Of course, nowadays we have plastic pails. For example, if I clean the kitchen floor (which I suspect not many of you men do ), I use my plastic pail, though I could also call it a bucket, too, I suppose.