Typically I would add any indexes initially that I know will be heavy hitters, then refine as needed based on actual use. Most databases provide tools to help identify missing indexes for common queries.
Also, if anyone reading this is using SQL Sever, do not use the recommended missing indexes it provides. They have a whole host of issues, including the ordering of columns and straight up recommend completely unnecessary indexes.
Use the query analyzer to figure out where it's doing table scans or similar, and you'll probably quickly see which index you need to create.
Keep in mind the database server tries to use indexes to minimize the amount of rows it needs to scan. So you just need enough to drastically cut down the number of rows to consider. If you have five columns in the where clause, think of which one or which combination is the most specific. This also means if you have a query with a where clause "colX = 1", yet 97% of the rows have colX equal to 1, adding and index on colX won't help. This means it can be customer-specific.
Also keep in mind that some database servers don't index null values, thus "where colX is null" means a table scan regardless. In such cases an alternative could be to add a computed column which would have a definite value, say "coalesce(colX, -1)" if colX should inly have positive values. You can then index on that, and tweak your queries to filter on the computed column.
Also keep in mind that if you have "order by", then the database server might ignore your index if it won't help in presenting the rows in the order dictated by the "order by" clause. We have some tables where we have multiple permutations of the same columns indexed due to this.
It's a skill and it's very database server dependent, just like learning to know the optimizer in your programming language of choice. Takes a fair bit of trial and error using the query analyzer.