When should I rebuild indexes?

 At the risk of being way too general to solve rebuilding indexes sql server in my answer, I will say that you should run an index maintenance process regularly. However, your index maintenance process should only rebuild/reorganize the indexes that specifically require it. This presents the question: when does an index require to be rebuilt or reorganized? Rolando touched on this nicely. Again, I risk being extremely broad. An index requires maintenance when the fragmentation level adversely affects performance. This level of fragmentation could vary based on the size and composition of the index. Speaking for SQL Server, I tend to choose a index size and index fragmentation level at which point I begin performing index maintenance. If an index contains less than 100 pages, I will perform no maintenance.

  If an index is between 10% and 30% fragmented, I will REORGANIZE the index and UPDATE the statistics. If an index is over 30% fragmented, I will REBUILD the index - with no UPDATE STATISTICS, as this is taken care of by the REBUILD. Remember though that a rebuild only updates the statistics object directly associated with the index. Other column statistics will need to be maintained separately to solve rebuilding indexes sql server.

This answer is really just a long way to say: Yes, you should do routine index maintenance, but only on the indexes that need it.