How does Checkpoint know which point to recover from in PostgreSQL?
How is the REDO location determined exactly. When a Checkpoint starts, does it literally say "REDO location is the current WAL record + 1"?


In essence, yes.  Exactly, no.  There is code in there about rounding up for cases where the record will not fit in the remainder of the log file and other corner cases.  To get an exact answer you have to read the source code.  See CreateCheckPoint in src/backend/access/transam/xlog.c


  When we do determine the REDO location, how is it that we are guaranteed that all WAL records before this are no longer needed?


A checkpoint starts (after computing the REDO pointer) by surveying all pages in the buffer cache, and marking the ones which were dirty at that time.  Before a checkpoint can end successfully, all of those marked pages need to have been written and flushed.  Once an initially dirty page has been flushed, the WAL that protected that initial dirtying of the page is no longer needed, because the page itself is safely on disk and can speak for itself.  If the page starts out dirty and is then re-dirtied multiple times throughout the checkpoint, then the subsequent dirtying actions will each have their own WAL records, which will necessarily fall after the REDO pointer.  Those WAL records will be retained, at least until the successful completion of the next checkpoint after the current one.