If it were possible to live forever, would our brains grow infinitely with the number of memories that we store? Or would we remove old memories as we create new ones?
You would need to live a long, long, long, long time for this to become remotely problematic.
Your question seems to suppose that a memory is "stored" by a neuron, and since neurons have mass, then the more memories we have the more our brains will weigh. Actually, neurogenesis is pretty rare in the adult brain--most of the cortex is fixed, and new neurons do not grow. (The hippocampus is the best known counterexample, but it's important to note that contrary to lore, the hippocampus doesn't store memories per sé, though it is involved in the formation and retrieval of memories).
Memories are represented in the brain as patterns of firing neurons. Let's say, for simplicity, that each neuron can either be on or off. Since there are 86 billion neurons in the brain, we can experience 2^86bn possible brain states. That's a lot.
Of course there are a lot of simplifications here--most notably, there is a lot of structure to the brain, and so i'm not suggesting you can store 2^86bn memories--but the logic is the same. Even with only 1,000 neurons, we can store a ridiculous amount of information (2^1000).
I would like to comment on MCM's answer as well, because I don't think it's true that we "remove" old memories. Or rather, the topic is still being debated in cognitive science today. For an old take on it, see renowned memory researcher Endel Tulving's (1974) article, in which he says:
When we forget something we once knew, it does not necessarily mean that the memory trace has been lost; it may only be inaccessible
So before you worry about this becoming a problem, I suspect you need to work out the secret of immortality first.
Tulving, E. (1974). Cue-Dependent Forgetting: When we forget something we once knew, it does not necessarily mean that the memory trace has been lost; it may only be inaccessible. American Scientist, 74-82.
We already remove old ones and create new ones. I doubt you remember most of Geometry, for instance.
As for capacity, this article from Scientific American gives a good overview of what we can estimate with our current knowledge.
For comparison, if your brain worked like a digital video recorder in a television, 2.5 petabytes would be enough to hold three million hours of TV shows. You would have to leave the TV running continuously for more than 300 years to use up all that storage.
The brain’s exact storage capacity for memories is difficult to calculate. First, we do not know how to measure the size of a memory. Second, certain memories involve more details and thus take up more space; other memories are forgotten and thus free up space. Additionally, some information is just not worth remembering in the first place.
So, there is an upper limit. Where is it? Well, probably a bit longer than our reasonable lifespan at the moment.
We already remove old memories (well, more properly unimportant ones) partially in order to make room for new ones
There are 3 different levels of storage, but none of them involve an increase of mass. (Distribution of mass, in one sense, but not amount thereof.) I'm not a neuroscientist, but there are one or two lurking around here who can correct anything wrong that I say, so don't take me as an authority. As I understand it: the first level is strictly electrochemical and very short-lived (except in some savants), such as what was the last word that you heard or the last time that you cracked your knuckles. Once the experience is over, it is forgotten. The second is just chemical, as proteins or whatever organize themselves into patterns that are essentially "books". That is what happens with stuff that you need to keep, such as school lessons, tax laws, or whatever. The third is DNA transcription, wherein a memory becomes an intrinsic part of your existence and might be inherited (as in "instinct" or even transplanted to another person.