When do you remove entries from a write-ahead log (WAL)?
First up, well done for trying to get to grips with how WAL works. It's often misunderstood but when people grasp the concept it's a genuine lightbulb moment for understanding databases.

We need to re-word your description of the steps that occur to commit a transaction:


Database documents the change in the write-ahead log (WAL).
Database updates the in-memory record.


That's it, we're done, the transaction is committed. The in-memory record is modified, details of what was modified is stored in the log, negating the need to harden every record change to physical disk.

On to your questions:


  When does the database know it's safe to remove the entry from the WAL?


The one liner explanation would be that the log entry isn't required once modified database records are flushed to disk. When this occurs is dependent on a variety of factors which vary according to the database. SQL Server for instance has a configurable recovery interval which controls the checkpoint frequency (the action of flushing changed records to disk).


  Does a WAL implying writing the record to disk twice (once in the WAL,
  once in the database file)?


Yes, kind of, no, depending on your perspective. Change a record once and the modification will be recorded to the log and when a checkpoint occurs, written to disk. Change the record 15 times between checkpoints and you have 15 changes recorded in the log but the modified record will only be written to disk once, on the next checkpoint.


  Postgres claims that WAL "significantly reduced number of disk writes,
  because only the log file needs to be flushed to disk" but (coming
  back to question #1) don't you have to flush the main database file
  before removing an entry from the WAL?


Yes you do but see above for why WAL reduces disk writes.