What I'm curious about is how postgres actually reads the pages into memory?
The engine reads the whole heap in any order while discarding rows marked as deleted. Hot blocks (already present in the cache) are much faster to process.
Does it organise them into some kind of ad-hoc in memory index whilst it reads them?
No, a sequential scan avoids indexes and reads the heap directly using buffering and the cache.
What if the table's too large to fit into memory?
A sequential scan is pipelined. This means I/O blocks are read as needed. The engine does not need to have the whole heap in memory before it starts processing it. It read a few blocks, then process them and discards them; then it does this again and again until it reads all the blocks of the heap.
Are there any high level papers on the topic?
There should be but, anyway, any good book on query optimization will describe this process in detail.
EDIT For Your Second Question:
What I guess I mean is if you're joining on some random column X, does it have to iterate through each possible row multiple times to find the correct row for each value in the other table, or does it do something more advanced than that?
Well, when you join a couple of tables (or more) the engine query planner produces a plan that includes a "Nested Loop", a "Hash Join", or a "Merge Join" operator. There are more operators but these are the common ones.
The Nested Loop Join retrieves rows for the linked table that match the first one. It could perform an index seek or scan on the related table (ideal) or a full table scan (not ideal).
The Hash Join hashes the secondary table first (incurring in high startup cost) and then joins fast.
The Merge Join sorts both tables by the join key (assuming an equi-join), again incurring in heavy startup cost) and then joins fast (like a zipper).
