It depends on the EEPROM you are using. Of course you can look up the maximum write cycle time (5 ms for most EEPROMs) and wait that long after each byte, but that's very unefficient.

Most EEPROMs have some way to detect when the write cycle has finished. For example, on some 8 kB STMicro EEPROMs, pin 1 is high as soon as the write cycle has been started and goes low as soon as it finishes. On some EEPROMs you can try reading the previous location while the EEPROM is still writing - it is supposed to give you the original value of some bit inverted on the output.
Again, this depends on the manufacturer, and in the data sheets you will usually find several methods to do this.

I'm using the pin 1 method with 8 kB EEPROMs, and writing one of them full usually takes 20 seconds or so, which is only about 2.5 ms/byte.