The data structure used at my work is fairly low level and it is amazing how much difference that makes in the performance. If you were to talk to an average web programmer about what an index was, most probably, they would have a very vague idea. This is because they can easily write statements like SELECT * FROM mytable WHERE mycolumn = 123 without much concern, and then move on. With the data structure at work it becomes apparent why this is a bad idea and why indexes are important. Without the index we have to manually step through each row and look for whatever the WHERE part of the query specifies. Just to give you an idea about what I mean, look at the SELECT statement, if mycolumn wasn’t the primary key then it probably wouldn’t be indexed by default; which would mean that you will end up iterating through all of the rows in that table!
I am guilty of not using indexes but as soon as I was exposed to indexes (before this job) I realized how important they were and quickly caught up to speed. I remember taking over for a project at my previous job where we had minimal number of indexes. The difference before and after the indexes was almost a ten folds! If indexes are always good then why not index every column? You have to be careful with indexes because just like everything else, indexes have good and bad parts. Every index adds to the time that it takes that database server to do an insert and some times updates because the database server has to do the extra step of actually indexing the column. Bottom line, make sure you know what indexes and use them when appropriate.
This and this pages are some further readings about indexes.