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:
So before you worry about this becoming a problem, I suspect you need to work out the secret of immortality first.
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.
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.