If you assume or want to adhere to relatively realistic biology of the brain (and leverage our ignorance of a lot of things related to it), there are a couple of factors to deal with (and things you can work with):
Cell counts and cell death:
We're assuming the source of immortality effectively defeats cell death from age-related causes (e.g. telomeres being restored via telomerase) and that ongoing radioactive exposure and other environmental factors do NOT in fact result in cancers (the saying is if you live long enough, you will get cancer, no matter what).
Your neuron count will largely stay the same once you reach adulthood (barring cell death due to various factors) except for a pool of stem cells that you're left with to expand those mental horizons. Even so, there's a limited pool (if not a very large one) of neurons to maintain everything from skills to memory and your personality.
Synaptic Plasticity and Memory:
With that limited pool, that means that memories, over the years, will likely fade as new ones are made. Neurons can adjust and change connections between themselves to strengthen memories and to change pathways as we live. While most of us, if we get old enough, will likely lose memories and functions due to decay or disease, an immortal would likely not. Instead, they'd just continue to make new memories (and perhaps learn new skills while enhancing existing ones).
I would argue, just like most adults don't remember the details of every day of their childhood (just the salient/memorable moments), an immortal will have memories that fade over time, something that might be a saving grace because traumas might have a chance of fading.
Life Experience:
We're all ultimately the culmination not just of our experiences but of the wisdom derived from those experiences. Our presence of mind (namely stemming from our interests in whatever the subject matter might be) defines just how much of those experiences we learn from and retain. If you aren't interested in a subject, you'll rarely retain much except those random facts that somehow got stored likely because something else was tied to it (e.g. environmental memory). And assuming we are focussed and healthy, we can generally accumulate a lot of knowledge...more than we often feel we should be able to.
When you talk to a fan who can quote stats across decades of a sport or someone who absolutely loves a topic and knows everything there is to know about it, remember that they also remember large portions of their lives, friends, family, people they hated, foods they loved, places they loved, people they admire, and so on. We store vast amounts of information in these squishy brains. :)
I think as you go on, say for a few hundred years or a thousand, you'd find that yes, you'd forget a name, or a face, you'll forget a song or the smell of a certain flower. There might be a mix of sadness associated with that (imagine how someone with dementia or Alzheimer's feels) and wonder (consider just how much knowledge you'll still have at your fingertips though). I could see someone like that, having learned that memories do fade even if it takes 100 years, taking on the same habits mortals take on (keeping photos, mementos, etc.). Meanwhile, there's something to be said about the confidence that stems from having a broad set of knowledge. I figure through just the sheer fact that they have the time for it to happen they'll accumulate a lot of knowledge. They may not be experts but they could piece together associations or bring ideas to a conversation or discussion that most people wouldn't think of simply because they don't have the breadth of knowledge someone like this would have.
Just one other thing to consider--something touched upon by some stories involving immortals: there is going to be some emotional scarring that results from seeing all of your family then all of your friends (including newly acquired ones) eventually getting old and dying. It can lead to defense mechanisms (like distancing themselves from mortals) which can definitely affect how they behave as the years go on. Plus, if they're trying to hide from society (e.g. Highlander), that creates a whole slew of stresses but also changes in behavior outside of the norm.
The other thing, which is sort of related to the latter part about their interactions with society, is the vampire grampa syndrome. In vampire stories, you often see super old vampires having trouble integrating with modern society. They were just fine with styles from 100 years ago. It's supposedly why they'd take a new victim to help them get up to speed with society and trends. Of course, they also tend to be separated and sequestered from general society so maybe not much of a concern?
Hope this helps.