After adding an index, ensuring that an index is actually used is probably the biggest win you will get in terms of performance in SqlServer. There are many ways that an query can be non-sargable, and therefore not using an available index, a common one is implicit (or even explicit) type conversion.
Within Denali ( or now SqlServer 2012 to give it its correct name) two new warnings have been added to the execution plan to help highlight this issue. “Type conversion in expression ColumnExpression may affect "CardinalityEstimate" in query plan choice” and “Type conversion in expression ColumnExpression may affect "SeekPlan" in query plan choice” are now shown if a type conversion has happened and it is affecting , or could be , affecting performance.
To demonstrate both I will need to populate a small table
drop table nums
create table nums
insert into nums(IntCol)
Select top(10) row_number() over(order by (select null)) from sys.columns
select * from nums where IntCol = 8
create index Idx1 on nums(IntCol)