When you look up the etymology of the word "meme", you find a bunch of stuff talking about its origins in Richard Dawkins's The Selfish Gene of course, originally as a term to refer to an idea that can be replicated via transmission between brains with corruption along the way, in analogy to how genes are replicated and corrupted via DNA. You also quickly find Godwin (of Godwin's Law fame) explaining the term and relating it to the internet in a 1994 Wired article (using something very close to its original meaning), and I've seen some quotes from the mid-2000s as well; though I believe these might be still referring to memes in the strictly Dawkinsian sense.
But of course one of the modern senses of "meme" is something more like "a specific instance of internet culture that can is copied and spread (more or less) verbatim, often but not always based on a template". It is kind of easy to see how this meaning might have evolved, but my recollection is I don't really recall seeing the term "meme" online so much through the noughties, maybe until the later part of that decade. Certainly it could have been particular to the circles I was in, but instead there were terms to describe specific types of (what we would today call) meme like "image macros" or "lolcats", and more general terms like "internet phenomena" or "internet references", but not widespread use of "meme". I note that Know Your Meme was launched as a project in September 2007 — was the term already in widespread use this early or was Know Your Meme perhaps influential in spreading it as a term or increasing its applicability?