Writing to Flash memory with Arduino Mega
Assuming you got the 5 volt version, hook up should be straight forward, although a bit cumbersome and it will likely require you to write some code. 

Connect the address, data, and enable pins from the flash to digital IO pins on the Arduino. Also connect the chip's Vdd to the Arduino +5VDC pin and the chip's Vss to an Arduino ground pin.

Configure all the pins connected to chip's address lines and enable lines to be digital out. 

To read a byte from the memory:

1) Configure the pins connected to the chip's data lines as digital input.
2) Set the pins connected to the address lines to the address you want to read.
3) Set the enable lines to CE=0, OE=0. 
4) Read the data byte from selected address from the pins connected to the data lines.

To write to the memory is similar but more complicated because flash requires you to erase a whole sector before you can start writing bytes inside that bank. You also need to wait for the write operation to complete, which typically takes ~20us for this chip.

All the reading and writing sequences are well documented in the data sheet here...

http://ww1.microchip.com/downloads/en/DeviceDoc/25022A.pdf

Be sure to publish your code so others in the same situation will not have to start from scratch!