Trying to stay database-neutral:
Indexes radically speed up ordering and filtering operations on a table - often by a factor of 1000 times or more. Compared to a phone book, an index lets you look up a single person up directly, because it's alread sorted alphabetically. If the phone book were just an unordered list of a million names with their phone numbers, you'd spend a month to find a single phone number.
As a natural consequence of keeping an index organized, it adds overhead to any change you perform on the data. To continue on the phonebook analogy, if you add a name, you're going to have to insert the name in the correct alphabetically order, and this takes more time/work than just adding the record to the end of the table.
An index will vastly improve the speed at which you find your data, but if you change a value in an indexed column, the data will have to physically move in the table in order to maintain the correct order.
Again, the index will help you find the record very quickly, compared to looking for the correct record in the entire table. Normally, a delete won't reorganize the index - it'll just leave a hole where the row was, though this may be different between database servers.
Changing data in an indexed table will take longer, while selecting data will be quite much faster with proper indexing. Like @ypercube says, over-indexing not only slows down change operations, it also forces the server to choose the correct index, which will take a long time if there are a thousand choices to go through.
There are fringe cases where you may not want to index a table: For instance, when you need to insert a large number of records, and you have no interest in filtering or ordering those records once you read them. I would, for instance, consider this for a fact table used (non-incrementally) for an OLAP cube - it gets populated once, and read in its entirety once without any particular sort order.