Does running a COUNT() statement using NOCOUNT ON; consume much
NOCOUNT does not mean "don't count" - it just means "don't report the count." Reporting can result in a lot of unnecessary chatter between server and client (which is usually ignored), and can incorrectly be interpreted as a result set by some APIs. At my previous jobs one of our coding policies was that SET NOCOUNT ON was required in every procedure, and I still promote it as a best practice. There are some APIs that rely on this message, however, and in fact your own .NET code may be relying on .RecordsAffected today.

As for the count, you can use sys.dm_db_partition_stats but be aware that this does not guarantee 100% accuracy - like taking a direct count with NOLOCK, it will not account for transactions in progress. 

I also suggest a couple of improvements on @garik's answer:

SELECT 
    sch = OBJECT_SCHEMA_NAME(i),
    obj = OBJECT_NAME(i),
    [RowCount] = rc
FROM 
(
    SELECT 
        i = [object_id],
        rc = SUM(row_count)
    FROM sys.dm_db_partition_stats
    WHERE index_id IN (0,1)
    GROUP BY [object_id]
) AS x
ORDER BY [RowCount] DESC;


This will take partitioning into account, includes the schema as well as object name, and identifies heaps and clustered indexes explicitly (who knows when Microsoft will start giving hypothetical indexes or other system-defined indexes negative index_id values).

EDIT: 

As for the question about counting on a primary key, you will see no difference in performance between COUNT(*) and COUNT(key_column) - if you inspect the plans, they should be identical. Be careful, though, about using COUNT(nullable_column) - personally I think COUNT(*) is safer. That said, for millions of rows, it is quite rarely a realistic requirement to get a 100% accurate count. Retrieving the row counts from the DMV above should be more than adequate and doesn't have a chance of impacting the table itself (or being slowed down by operations on the table).