When I was very young, I watched cartoon like most kids. I liked various animal characters, such as Donald Duck. I remember reading a short story involving a kid being transformed into a duck by a witch.
As I grew older, I gravitated towards various furry things, mostly cartoons and some comics. At the age of about 7, I watched The Secret of NIMH in the theaters (I saw a later release as I was living overseas at the time) and for the first time I dreamt of myself as a furry. Very strong vivid dreams that repeated several nights.
Time went on, as a teen I watched cartoons still and read animal themed books (not exclusively, just when I could find them) and collected furry themed RPGs. One of the books I read was Watership Down by Richard Adams.
Again time passed, and I was in college. I got a part time job as a computer lab monitor for the statistics lab (I was a computer science major myself) and wanted to waste time. I had not really used the web before, just used local bulletin boards. I searched for things on the web that I liked at the time; movies, books, that kind of thing. I searched for "Watership Down" and got a link to FurryMUCK. This was my first exposure to the word Furry, and it intrigued me to know others had similar interests. I researched furry, and learned of both the "dark side" and the "light side" of the fandom, and decided to join in anyway. I was in my early 20s and finally connected to people I could feel at home with discussing my interests.
So yeah, long story, but that is how I found the fandom.