This is a question that came up on Interview Question: will SQL Server always do a table scan to find the result of SELECT COUNT (*) FROM mytable?
The answer is no. The query processor will use the index with the smallest number of pages - i.e. with the least I/O cost.
Let me quickly show you. First I'll create a simple table with no indexes.

CREATE TABLE CTest (c1 INT IDENTITY, c2 BIGINT DEFAULT 1, c3 CHAR (1000) DEFAULT 'a');
GO
SET NOCOUNT ON;
GO
INSERT INTO CTest DEFAULT VALUES;
GO 10000

Don't forget to unclick the Include Actual Query Plan button
 
before running the 10000 inserts otherwise it will take forever (generating 10000 graphical plans) and SSMS will barf with:

The query has exceeded the maximum number of result sets that can be displayed in the Execution Plan pane. Only the first 250 result sets are displayed in the Execution Plan pane.

Now if we do the SELECT COUNT (*), the plan is:
 
The query processor has no choice but to do a table scan.
Now I'll add a nonclustered index that will have less pages that the table itself:

CREATE NONCLUSTERED INDEX CTest_1 ON CTest (c2);
GO

And the select plan is now:
 
Notice that the Table Scan operator has changed to an Index Scan operator on the new CTest_1 index. This is because the nonclustered index has fewer pages than the table and so the I/O cost is lower.
Now I'll create an index that's even smaller, over the integer column:

CREATE NONCLUSTERED INDEX CTest_2 ON CTest (c1);
GO

And the plan should change to use the smallest index again:
 
And it does, as I expected.
Let's look at the relative page counts for each index and the table:

SELECT [index_id], [page_count]
FROM sys.dm_db_index_physical_stats (DB_ID (), OBJECT_ID ('CTest'), NULL, NULL, 'LIMITED');
GO
index_id    page_count
----------- --------------------
0           1436
2           28
3           19

Any time the query processor is working out what plan to use, one of the key factors in plan choice is the I/O cost.
Hope this helps!