Methods with 'or' or 'and' in their names
It's a pretty good sign that you're doing too much in a single method if it has the word 'and' in its name. For example, addMessageAndNotifyUser() should probably be split into two methods: addMessage() and notifyUser().
Methods with 'or' in their name aren't as easy to classify. If the whole method is just a single conditional, the method name may make perfect sense. I would argue that it is just poorly named.
Methods with almost the same name
If you've got multiple methods that all have basically the same name except for a useless word, you're probably making the code harder to understand. For example if you wanted to add a message, which of these would you call?
If the first addMessage calls one of the other ones, is adding a message its main task? Could it be renamed to something that makes more sense?
Methods that start with 'do'
Do is always a wasted word. I see this mostly from coders that got their start with Visual Basic. Just don't 'do' it.
Why does it matter?
Readability is the most important thing to strive for in code. Bug free, maintainable, and fast code come from code that is readable. Most of the code's life cycle is spent in maintenance. The longest part of a typical maintenance task is to figure out what a particular piece of code is trying to do. Good documentation goes a long way towards making code understandable, but if the methods are actually well named you won't even need to look at the documentation.
Update (2012-03-15): I felt the need to revisit this post. Poor naming in the code base I'm working on wasted several hours of my day. I was trying to find where a set of objects was getting loaded from our data store. Looking through other code that did the same type of thing was a deep rabbit hole of included files and static calls to other classes. Finally I asked a teammate where the objects get loaded. He pointed out that they were loaded in a method named 'handleSortingAndPagination'. The method name doesn't provide any hint that it loads the objects from the data store before sorting and paginating them. The documentation for the method didn't either. This adds another bad naming smell: names that do not reflect what the method does.