When should a method be static?
Solution 1:
Make methods static when they are not part of the instance. Don't sweat the micro-optimisations.
You might find you have lots of private methods that could be static but you always call from instance methods (or each other). In that case it doesn't really matter that much. However, if you want to actually be able to test your code, and perhaps use it from elsewhere, you might want to consider making those static methods in a different, non-instantiable class.
Solution 2:
Whether or not a method is static is more of a design consideration than one of efficiency. A static method belongs to a class, where a non-static method belongs to an object. If you had a Math class, you might have a few static methods to deal with addition and subtraction because these are concepts associated with Math. However, if you had a Car class, you might have a few non-static methods to change gears and steer, because those are associated with a specific car, and not the concept of cars in general.
Solution 3:
Another problem with static methods is that it is quite painful to write unit tests for them - in Java, at least. You cannot mock a static method in any way. There is a post on google testing blog about this issue.
My rule of thumb is to write static methods only when they have no external dependencies (like database access, read files, emails and so on) to keep them as simple as possible.
Solution 4:
Just remember that whenever you are writing a static method, you are writing an inflexible method that cannot have it's behavior modified very easily.
You are writing procedural code, so if it makes sense to be procedural, then do it. If not, it should probably be an instance method.
This idea is taken from an article by Steve Yegge, which I think is an interesting and useful read.