This question depends heavily on what it is Data is expected to remember, and how long he is going to live. Naturally, if he lives forever then no amount of storage is enough. Additionally, if he records an exabyte a minute he's going to run out of storage almost immediately. But we can make some assumptions and see how they turn out.
First, we're going with the limit that Data can store a total of 800 quadrillion bits as mentioned in The Measure of a Man. This is exactly 100 petabytes, or roughly 88.8 pebibytes. For comparison, this is about 250 times more memory than that taken up by every book ever written in any language, or about 2,000,000 blu ray discs. We're assuming that this is memory intended exclusively to record the day to day happenings of Data and won't need to be shared with other things relating to his programming and function.
Now the real question is: How much data does Data save every day? Things like smell, taste and touch are hard to quantify, but sight and sound are not. If we assume that Data simply keeps a running record of everything he sees and hears, then the question instead becomes how high his resolution is, how many frames per second, and what codecs he use. For simplicity's sake we'll assume he saves video at a 16-bit RGB standard (likely much higher), giving 6 bytes per pixel.
Uncompressed, a 1280x720@25 video stream would require ~138MB per second, or ~12TB per day. Assuming an audio bit rate of 320 kbps would only add some ~28GB per day, so it's pretty negligible, giving Data the capacity to store about ~23 years of his life.
This is obviously not the case since not only did Data live for at least 40 years, it would also be a humongous waste to not compress anything. Modern lossless video codecs could bring those size estimates down by as much as 50% (though the average compression would be much lower than that), bringing the daily storage requirements down to ~6TB. Lossy video codecs could bring the estimates down to a minuscule fraction in the gigabyte range, potentially giving Data thousands of years of storage.
1280x720@25 with 16 bit colors and 320 kbps audio is pretty low quality given what we've seen of Data's capability. But there are things we can speculate that his codecs are capable of, which would allow us to up the resolution and frame rate significantly, and still give Data a reasonable life span. For example, the codec could be capable of removing the undoubtedly massive amounts of redundant frames, compressing the information in those that are repeated hourly or daily or weekly or monthly but not in sequence. Text could be transcribed, repeated pictures and sounds could be stored and referenced. If an oft seen room was mapped as a 3D model, frames taken in those rooms could instead just store Data's position and viewing angle, then remove everything in the frame but the deviations and additions, like people and furniture. There's a lot of things you can do with 24 hour video, if it's recorded from the perspective of someone with fairly undeviating routines. Some of it is beyond our current day capability, but surely not beyond someone who can make a hard AI.
There's a lot of other things Data probably saves as well: His thoughts, other sensory readings, conclusions drawn, but if they can be transcribed as text their additional storage requirements are negligible.
TL;DR Given a few (a lot) assumptions about what kind of data Data stores, and the compression capabilities of the 24th century, 100 petabytes should be more than enough to keep Data going for a long time.
