My collection started simply with what I bought over the years as a kid. I was never the kid that would trade in his entire collection of one system's games in order to get the next gen. That being said - my family wasn't rich growing up, so I didn't exactly accumulate a TON of stuff. Now that I'm out of college and working, I'm able to afford a lot more.
My initial goal was simply to collect every NES and SNES game I had ever rented or played as a kid. Nostalgia was the biggest factor in my game collection. There were a few select titles that I shelled out for because I wanted them immediately (Castlevania III, the Ninja Gaiden games, etc) - but for the most part I've been able to build up through the help of thrift stores. Just because you live in a small town doesn't mean you can't find stuff! The thrift store in my home town (less than 10,000 people) just had a stack of 9 mint condition Saturn games for a buck a piece. My dad found me a stack of 9 Virtual Boy games (including Wario Land! Booyah!) at a neighboring town's thrift store for a grand total of five bucks.
When starting though it's important to have focus (as many others have said earlier). Once you have the stuff you really want - it's fun to buy the extra stuff when you run across it. I just got a Dreamcast and Saturn in the last month. I had never played these systems growing up, but it's easy to collect for them now that I have accumulated the stuff I really wanted. Now when I run into other random games and systems at a thrift store it's a bonus.
In the meantime I continue to buy the modern games that interest me, and have no plans to get rid of any of those anytime soon

I too recommend only going to ebay and amazon for your absolute must have games - otherwise it can get really pricey really fast. As your collection grows you'll figure out what exactly you're willing to spend for what. Stay organized and keep things on shelves! It will give you a greater sense of accomplishment and make things easier to find when your collection gets massive!