They wouldn't hit the max capacity in hundreds of years.
Human memory is fairly huge, estimated to be at 8 petabytes, enough to record 3 million hours which is enough to store around 300 years of video. It's hard to estimate exactly how that correlates to memory, but it's probably enough to remember a decent slice of your life.
In thousands of years you would likely start to hit the cap. The immortality process would likely already have methods to prune neurones and connections and replace them when damaged, and they'd either lose random memories or need to prune some aspects of their past.
Of course, how well you remember depends on how well you consolidate long term memories. I don't remember everything I did yesterday, and my mind likely dumped most memories of that as unimportant. Events decades or centuries ago will likely be quite hard to recall if a focused effort isn't made to remember them.
Some millenia old people would likely have the discipline to remember well the past, by working to consolidate key memories. Some wouldn't care, and would forget all but the strongest of memories that were repeated across their memory.