According to Postgres documentation: http://www.postgresql.org/docs/9.1/static/sql-vacuum.html
Plain VACUUM (without FULL) simply reclaims space and makes it available for re-use. This form of the command can operate in parallel with normal reading and writing of the table, as an exclusive lock is not obtained. However, extra space is not returned to the operating system (in most cases); it's just kept available for re-use within the same table.
VACUUM FULL rewrites the entire contents of the table into a new disk file with no extra space, allowing unused space to be returned to the operating system. This form is much slower and requires an exclusive lock on each table while it is being processed
So autovacuum will recycle the space used by dead tuples to be reused by new tuples and will keep the table in at a reasonable size, but it won't reclaim the space if the table is already bloated. To reclaim the space, you can either
Dump the table to a file, drop the table, and then re-import the table.