One counter places bytes sequentially in the array, while another tracks removal. Unlike a conventional RAM, you can read and write from most FIFOs at the same time. Each data byte is strobed into the device with the write line. If the FIFO is 1k deep, than, assuming no reads take place, after 1024 write cycles the FIFO Full flag is asserted and each additional write generally deletes the oldest data and clocks in the new. Thus, just like a software FIFO, it keeps only the most recent 1024 data items.
Any read pulls the oldest saved data from the chip.
If the device was full, a single read will clear the FIFO Full flag. In most applications data is being written and read from the device asynchronously, the Full, Empty, and Half-Full flags may be toggling erratically to reflect the chaotic nature of the synchronization between input and output devices. Different devices behave in startling different ways. I've used the IDT 7100 family extensively, and have found that once you exceed the chip's depth, it does in fact not start to save the newest data only. In fact, it stops accepting new data entirely.