Define a proper index for a table I have a table with millions of rows and something like 20 columns. This table have an unique identifier as primary key, but the most likely query is based on three varchar columns (col1 and col2 of type nvarchar(35) and col3 of type nvarchar(14)). For a given {col1, col2, col3} correspond at maximum 1 row. col3 is the less fragmented column. In the vast majority of cases, the table will be stressed with query like this:

SELECT * FROM table
    WHERE col1 = "xxx0" AND col2 = "yyy0" AND col3 = "zzz0"
    OR col1 = "xxx1" AND col2 = "yyy1" AND col3 = "zzz1"
    ...
    OR col1 = "xxxn" AND col2 = "yyyn" AND col3 = "zzzn"


Given this situation? What will be a good indexing strategy? Multi-column with col3 as first column? Three separated indexes?
A composite index with any order of col1,col2,col3 would work here. The query you have shown in the question would be able to perform three seeks into it for the three or-ed predicates.

To determine the best order out of the 6 possible permutations I would first look at other queries, or alternatively you could look at the missing index DMVs. Quite likely you will find that the choices you make optimising this one query can help optimise others too.

If you have queries that perform equality seeks using just two of the columns then put them first so the same index supports those queries. And similarly if one of those columns is often used on its own in an equality or range predicate then make that the leading one. 

Though if any of the columns is not particularly selective you would need to verify that the index is actually used for the query identified by the process above and consider whether it is worth adding included columns to make it covering if not (or considering a different index order that would benefit a different query).