Check that all columns where searches or sorts take place are indexed unless tables are very small or have high levels of updates. One place where indexes are overlooked (and very necessary) is on the parent column of a foreign key relationship.
Consider adding to an index all the columns needed by frequent queries so those queries dont have to look up both index and table data.
Tables physical order on disk should reflect the order needed by queries that retrieve the largest number of rows (this could result in a table thats not in primary key order).
Column order matters when creating indexes. The column that does the most to narrow down the size of the final result set should be first in the index.
Be sure that table data distribution statistics are calculated and kept up-to-date. Missing or incorrect statistics can result in disastrously slow queries.
Once the database is in final shape, inspect query execution plans and use provided query and index analysis tools to be sure nothing major was missed.
For better performance, rewrite SQL queries to remove subselects.
Continue to monitor performance issues (such as tracking the most resource-intensive queries) to see how tuning might change to support current usage.