Should css class names like 'floatleft' that directly describe the attached style be avoided?

It's great until you re-design, and narrow is highlighted yellow, center converts better left-justified, and the image you called floatleft now belongs on the right.

I'll admit to the sin of using floatleft and clear as CSS class names, but it is much easier to maintain your CSS if you choose names that relate to the semantic meaning of the content, like feedback and heroimage.

Presentational class names

The HTML spec is clear on this issue:

There are no additional restrictions on the tokens authors can use in the class attribute, but authors are encouraged to use values that describe the nature of the content, rather than values that describe the desired presentation of the content.

Does clearleft describe the nature of the content? Not really. Eric Meyer made a joke about this a while ago.

Try to find a structural relation between the seemingly unrelated elements

Let's say you have paragraphs about ducks, paragraphs about monkeys and paragraphs about frogs. You want them have a blue background.

<p class="duck"></p>
<p class="monkey"></p>
<p class="frog"></p>

You could add this CSS rule:

p.duck, p.monkey, p.frog {
    background-color: blue;
}

But aren't they all animals? Just add another animal token:

<p class="animal duck"></p>
<p class="animal monkey"></p>
<p class="animal frog"></p>

And change the CSS rule to:

p.animal {
    background-color: blue;
}

It is hard and it might not always be possible but the important thing is not to give up quickly.

What if you can't?

If you have a lot of elements with absolutely no structural relation between them, that indicates a structural problem with your document. Try to decrease these elements. That said, grouping n CSS selectors on one rule is still better than adding n presentational class tokens in your HTML document.

Style classes should be semantic. This is a great article on semantic web page design (well, I found it really helpful anyway).

EDIT: I just read another article that makes some good points for using things like display: inline-block, display: table etc. instead of floats. That should help avoid those pesky floatleft and clearfix classes. Making them semantic is always up to you though.