Yes, an EEPROM is a type of nonvolatile memory which can hold data even without any power for a significant amount of time (the actual time depends on temperature and other conditions).
There are a few other non volatile solutions for you to consider:
1) Internal Flash memory - Most microcontrollers nowdays have Flash for code storage and some provide it for user data and logging as well. This also has limited write cycles and requires block erase before changing bits from '1' to '0' (you store data elsewhere in the meantime and then rewrite it).
2) Internal FRAM memory - TI has devices with FRAM memory which is nonvolatile, can be accessed very simply (like any other memory location. Reads are also destructive as writes (though in your case this might not matter since the number of cycles is 10^13 or so at 85 degrees celsius).
3) External Flash memory - You can add memory externally to hold a few megabits of data rather inexpensively.
Depending on the rate at which you want to save (and whether you can shutdown nicely) you might be able to increase the effective number of cycles available for you.
No, your reasoning is not correct.
Firstly, let's look at your maths.
The device is 256kbits. That means that it contains an array of 32kbytes, which equals 32768 bytes.
32768 is 215, so an address can be represented using 15 bits, or rounded up, just 2 bytes.
That is, you have addresses 00000000 00000000 to 01111111 11111111.
You can tell all that by looking at figure 5-2 in the datasheet you linked to:
So after sending the control byte you then send 2 address bytes. Any data bytes follow that sequence. So yes, that is three bytes in total, but only two of them are the address.
Setting that address only needs to be done once per write sequence. You aren't limited to just writing one byte.
Once you have set the address you can write up to 64 bytes (or up to the end of the current 64-byte page) without having to send a new address. So you could set the address to 23 and then write bytes 23, 24, 25, 26, 27. That would be a total of 3 bytes for the control + address, then 5 bytes for the data totalling 8 bytes. If you calculate 8/5, you get 1.6, which could be said to be the transaction "efficiency". For every byte of EEPROM you write like that you need 1.6 bytes to do it. Writing more bytes at a time improves that efficiency.
The best efficiency is to write an entire page at once, which would be \$\frac{3+64}{64}=1.046875\$.
When it comes to reading things are slightly different. This is because the chip maintains its own internal address pointer for reading. Once you have set the address it automatically increments to the next address after reading.
Setting the address takes 3 bytes as before - the control byte plus the two address bytes. But then to actually read you need to perform another transaction with another control byte. So to read one byte takes 1+2+1+1 bytes. That would be an efficiency of \$\frac{1+2+1+1}{1}=5\$ which is not that efficient at all. Things get much more efficient though if you make use of that internal address pointer and read multiple bytes. To take the example addresses we used for writing, the efficiency for reading would be \$\frac{1+2+1+5}{5}=1.8\$ - a huge increase in efficiency.
So there are other small tricks you can use. If you want to read two bytes that are close to each other in EEPROM it can actually be more efficient to do a sequential read of the entire memory between the two bytes of interest and throw away the bytes you're not interested in.
And yes, this is pretty much typical of all EEPROM devices in this class. But then they're not really intended to be particularly fast - they are intended to contain small amounts of configuration information for a system which is read once during startup and not referenced that much from then on. For faster, heavier throughput you would normally use a serial Flash device instead of EEPROM. They are greater capacity and more efficient to access, but writing to them is more convoluted since you have to erase an entire page before writing it. They are often used these days as the BIOS chips in computers - especially laptops - where there's a lot of reading and not much writing.
Best Answer
With PICs in particular, sometimes you find what you need in the Family Reference Manual as opposed to the data sheet. In this case, the mid-range family ref manual has a chapter on architecture that you might find of use, and its in a different tone than the chip's datasheet.
For PICs datasheets tend to have a ton of chip specific info,but the Family Ref Manuals tend to show a more global picture.