With the eeprom you describe you can interface it much like an eprom except you can write to it. When you write to it, you must wait a specified time (around 10 milliseconds) for the device to write the value. During that time the device is 'off the air' - you cannot read or write to it during this time.

The difference between flash and eeprom is that with flash you must write a block of data (this can vary from 128 bytes upwards) at a time whereas with eeprom you can write a byte at a time. Flash has higher density and is normally cheaper. Flash is good in cases where you don't change the data too often, eeprom is used where you expect to change the data frequently. Note that both flash and eeprom have a 'write endurance' which specifies the number of writes you can do to a block or byte before wearing it out. There is quite a few differences between manufacturers with these devices- refer to the datasheet for your exact part for information.

Remember, if you use flash or eeprom to store your code and you want to upload new code to it say via the serial port, as soon as you write that device, you can no longer execute code from it whilst the write is in progress! You have a couple of choices here, either have some ram mapped into the code space and copy the write routines into this ram or have another eprom or flash that has the write code in it.