What is held in memory during the life of a CTE? Assuming a multi-read/multi-write CTE, what exactly is held in memory during the life of the statement?

Is all data except RETURNING data discarded at the end of each sub-statement?
A CTE term's output is accumulated into a TupleStore. A TupleStore may internally be in-memory or may spill to disk. See src/include/utils/tuplestore.h and src/backend/utils/sort/tuplestore.c, particularly the comment at the top of tuplestore.c.

For a wCTE that'll be the RETURNING output for that term.

To determine whether anything else is retained requires analysis of the memory contexts in which each CTE term is executed, as PostgreSQL uses a hierarchical memory context based allocator.  Here you need to look at src/backend/executor/nodeCtescan.c. It's pretty complicated, but a read of CteScanNext suggests that the queries are often executing concurrently, with one query consuming the results of another.

So. While memory might be freed at the end of each sub-statement (CTE term) there's no gurarantee that any of the CTE terms finish at any particular time.

Rephrasing your question:


  Is all in-memory data from a CTE term except RETURNING data discarded before the next CTE term executes


the answer is "no".

However, that doesn't mean PostgreSQL will keep piles of data in memory. It frequently discards rows as soon as it's done with them and never needs to see them again. It can spill big temporary results to tempfiles on disk. If it materialises, sorts or aggegates query output it will generally throw away the un-aggregated/un-sorted data after it finishes. etc.