OK, slightly against the tradition of TDWTF, I'll give you a bit of an answer.
In general, table indexes give you much much faster access to the data IF you use the indexed column(s) in your selection critiera. If you have a telephone directory, then it is assumed that you are going to use last name & initials to do the lookup, which you can probably do in say 20 seconds. If someone asked you to find an entry based on street number and street name, then the only way to do it would be to read every single entry in the book until you found it.
So in your index-less database, every query will be scanning all the data in the table. This isn't a problem in a teeny database, but when the tables get big it's a disaster. So you need to work out what key columns are going to be used as selection criteria, and create indexes using those columns. This will improve performance many hundreds of times, as with the phone directory.
Typically, you should have one unique index (e.g. customer ID number) which both ups performance and also documents what the unique key of the table is, and optionally other indexes just for performance. So, in a customer table, you might also put an index (non-unique) on State/Town, if you were expecting to select records by State, or by State/Town combination.
The tradeoff is that indexes take up space and have to be kept updated (internally). They are essentially a sorted list of the values of the columns in your index, and a pointer to the page where that entry is found. So, in your phone directory example, you *could* create an index of every entry sorted by street name, pointing you to the pages where those entries are found, but it would need a new book to keep the list in - small overhead. In addition, when you insert a new record into your table, all the indexes have to be updated, which may involve some shuffling around, so insert/update performance will be a bit slower. This is why you don't put an index on every single column.
Understanding indexes and the query optimiser for your particular dbms is crucial; it's really the whole 'point' of databases - fast access by key.
Here endeth the lesson. Everyone stop yawning please.