Should I index my database table(s), and if so, how?

An index is like a set of pointers to specific rows in a table. These pointers are ordered in terms of the column(s) defined by the index, which makes SQL's scans much more efficient - they just look up the pointers to the rows with the relevant data (based on a WHERE or other clause), and jump right to the row(s). 
 
If you have multiple indexes on one column each, there will be n sets of pointers to the rows - each ordered by the specific column. As I will discuss later, you should choose your index(es) wisely. 
 
If you have one index on multiple columns, it creates one huge set of pointers -- ordering the rows by each column you chose, successively.  
 
So let's say you have a table with three integer columns (a, b and c). Let's insert some sample data, which are stored on disk in heap format [remember - tables are not guaranteed to be sorted in any way], looking like this (a normal SELECT a,b,c FROM table, given some fictitious data): 
 

a b c  -----  1 2 3  2 2 2  1 2 2  3 1 2  2 1 2

 
Now, in the first example, we'll create a multi-column index on a, b and c. Now, this is how the pointers will look, ORDER BY a, b, c: 
 

a b c  -----  1 2 2  1 2 3  2 1 2  2 2 2  3 1 2

 
So now, imagine running a query SELECT a,b,c FROM table WHERE a=1. This query will be very efficient, because the pointers have grouped these records all together. 
 
Now, imagine running a similar query, but this time SELECT a,b,c FROM table WHERE b=1. This query will not be very efficient, since SQL Server's only index option is this index which does NOT consider b to be a top priority (and it just so happens that these records are NOT grouped together). It's the jumping around on the pointers that makes SQL Server work harder to get all the rows that match the WHERE clause - in some cases it may be more efficient for SQL Server to just do a table scan, rather than care about your index. 
 
Let's create multiple indexes now, one on each column. The pointers for each, in order, will look something like this: 
 

a b c  -----  1 2 2  1 2 3  2 1 2  2 2 2  3 1 2

 
 

a b c  -----  2 1 2  3 1 2  1 2 2  1 2 3  2 2 2

 
 

a b c  -----  1 2 2  2 1 2  2 2 2  3 1 2  1 2 3

 
Now, running the two queries mentioned above, each will be very efficient. In the first query, SQL Server will choose the first index, and get all the rows where a is grouped together - minimizing read / scan time. In the second query, SQL Server is smart enough to ignore the first index, and use the second index instead. 
 
I will mention that with a compound index, let's say columns a, b and c, the optimizer will use the index for a query on column a, or a and b, or a and b and c, or a and c. However, the index will not be able to optimize on queries against column b, column c, or columns b and c. 
 
Keep in mind that while an index can speed up SELECTs, it can also can slow down INSERTs and UPDATEs. In addition, an index occupies disk space, which can be an issue not only for performance but also for backup / replication purposes. Just something you should keep in mind before adding 19,000 indexes to a database - there is definitely a happy medium between no indexes and too many. 
 
Indexing in and of itself is a science, and is not easy to master without spending a lot of time analyzing different indexes and their impacts on performance and disk space. And I didn't even start getting into fragmentation, partitioning, clustered indexes, compound indexes... 
 
What you use and what will work best depends on your schema, the nature of your queries, where your performance counts, the load on your system, hardware, levels of transactions, acceptable query times, type of application, etc. I strongly recommend running Index Tuning Wizard, feeding it a SQL trace of the typical activity on your system. The wizard should identify which types of indexes will work best for your scenario.