How does the OS know/keep track of what part of physical ram is free, so it can map the virtual page address in the page table to a physical frame in ram on a page fault?
The OS must maintain data structures keeping track of the usage of every page frame of the physical memory. How this is done is dependent on the OS — below is a simplified description of how Linux does this.
The Linux kernel has an array of page descriptors, one for each page frame in RAM. Which page frame a page descriptor corresponds to is determined by the index of the page descriptor in the descriptor array. Each descriptor contains, among other things, an assortment of flags as well as a reference count governing whether or not the page is free.
On top of the page descriptor array, Linux implements the Buddy Memory Allocation system to group free page frames into lists containing groups of contiguous page frames. The first list contains descriptors of single page frames, the second groups of two contiguous page frames, the third groups of four contiguous page frames, and so on. Blocks are always allocated in sizes of 2k pages. When a request of order k succeeds, the block is removed from the free list k. If no block is available on list k, a block on a higher-order list can be split up and the remaining parts are moved to lower-order lists as appropriate.
The memory is kept track by the MMU (memory management unit). The MMU is a piece of hardware that is a part of the CPU. With older hardware, the MMU could be a separate from the CPU.
The MMU has what is called a page table. The page table maps the virtual page numbers to the physical page numbers in the main memory. Typically each virtual memory location or "page" is a couple of kilobytes. Each of these mappings are individually kept track of in the page table. These are known as page table entries (PTE).
When a page fault happens, the MMU sends a signal back to the CPU letting it know that a fault has occurred. The OS then then tries to find a spare frame of RAM and and then requests a PTE to map the virtual address to the physical address.
Of course this is a very brief answer, on something that can be very in-depth and complex. If you want to learn more, I'd start with reading about MMU, virtual addresses and some basic memory management.
To slightly expand upon DrZoo's answer, the operating system is ultimately responsible for (somehow ...) knowing the present status and ownership of all physical-storage "pages." It is also responsible for knowing the virtual situation of every process.
It must know this in order to set up the physical data-structures that the MMU uses, and to know what commands to give to that unit at various appropriate times.
Every operating system necessarily has some sort of data-structure arrangement which enables it to keep track of this, and every operating system does it differently.