Best strategy for apply indexes to ORACLE tables

I agree with everything said above.

You cannot index based on a design.  You need to index on use.  Keep in mind that just because an index exists doesn't mean using it is the 'best' performance.

This is why Oracle came up the the Cost Based Optimizer (CBO).  This takes table statistics and, most of the time, comes up with the 'most optimized', therefore 'best' execution plan.

It does get things wrong at times and you can over-ride it with hints.  Most of the time it does get it right.

You need to monitor performance and tune based on what you observe.

If you are licensed for the diagnostics or performance packs check out AWR and ADDM.

If not, check out StatsPack.

>>> We're starting to see our queries slow down

There's your answer. Tune the queries that are causing your customers pain. Prioritize by the cost ($) associated with that pain vs cost ($) to address it.

If you don't know what to index.  Look at some of those slow queries.  At the most basic level, start with the where clauses.

If this query is slow:

select col1,col2,col3 from some_table where colx=1,coly=2, colz=3;

I would suggest an index on colx,coly,colz  
(one index on 3 columns,  not 3 indexes of one column each)

As mentioned above, indexes aren't guaranteed to  help; but if you really do have no indexes at all in your schema, then you'll probably see some marked improvement with a few simple targeted additions for the biggest pain points.