Sebastiano's correct. As to how it gets them it gets them the same way it would get them in a concurrent session which started a SELECT before you did the DELETE/COMMIT statements - the rollback segment.
This is where the complexity lies in implementing an overwriting storage manager, and why there's a certain appeal in the non-overwriting storage manager used by PostgreSQL (offset by the need to reclaim space).
As to how PG implements transaction semantics, each tuple is tagged with transaction id information that identifies the transaction "window" (my term) within which the tuple is visible. The transaction id is bumped for each new transaction. Deleting a tuple involves setting its "window" such that the tuple is no longer visible after the transaction zapping it. If you think about this implementation you can see why high concurrency and row-level locking was fairly easy to implement on top of it.
VACUUM runs through the table looking for "dead" tuples, i.e. tuples that can't be seen by any currently running or future transaction. In older PG (and PG 7.2's VACUUM FULL command) the table's compacted and unneeded blocks thrown away. PG 7.2's new, lighter-weight VACUUM just frees up space within blocks rather than compact the entire table, and maintains a free list for each table which allows it to reuse the space when future tuples are inserted. It only throws away totally empty blocks at the end of the table and only if no other backend has locked the block. At least that's my understanding, I haven't studied it in detail.
