Thanks to MVCC PostgreSQL does a pretty good job at avoiding locking contentions. Unfortunately this ability does not come without a cost. In this case the cost is having to run vacuum from time to time (the best interval for you will depend on usage) to recover rows and make that space available again. This is especially true on a table that is changing a lot (INSERT, UPDATE and DELETE). If you don’t do this you’ll notice things slowing down, just like Karl noticed with SELECT count(*). Setting aside the question of doing SELECT count(*) on a table for now, if you have a table that is getting millions of changes a day then you better be looking at how often you need to run vacuum. If it takes you years to hit a million changes then running vacuum won’t need to be as frequent.
I’ve not played with pg_autovacuum yet, but that is another resource to look at for determining how often you need to vacuum your tables.