1) Using sysindexes.rows (or any approach based on metadata from the system tables) is not guaranteed to give an accurate value. If you just need an approximate answer as quickly as possible great, otherwise use COUNT().
2) Be careful with your ON and WHERE clauses across a linked server boundary - in Ramesh's example there's a varchar-based WHERE condition, and unless you've got your collation settings matched up correctly between local and remote servers you can end up with the remote table being pulled across to the local server before the conditions are resolved. It's much better to encapsulate your linked server logic into a stored proc on the remote server so that all of its conditions are resolved on that server, and simply EXEC it from the local server. The resulting data can be either INSERT... EXECed into a local table or passed back with OUTPUT params.