In short, they can be very usefull if your data distribution on a particular table is very skewed.

For example, let's say you have 10000 rows in a table. On some indexed column col1 you have 5000 distinct values. So for CBO, you have on avarage 2 rows per key. So when you isue some query with condition:
... WHERE col1=0 ....
optimizer will probably find it very efficient to use that index.

But in reality you might have the situation that you have 5000 rows with value col1=0 and the remaining 5000 rows having all other distinct values. Without having histograms, CBO can not be aware that full table scan would be much more efficient than index scan for that particular query. But if you have proper histograms for that indexed column, CBO will have much more information about the actual data distribution and can choose much better execution plan.

When are histograms useless? probably in cases where:
- Data distribution is even, so that avarages are quite reliable and sufficient.
- You use bind variables. In that case histograms are useless, because the actual values used in the WHERE condition are not known at parse time, when the optimal execution path is determined (actual values are bound to the query only at execution time, when execution path is allready determined).