Hobby and model stores
Hobby stores have almost everything you'll need to build a robot. However, if you were to request a certain item that you'll be using for your robot, they might act as if that part was never invented. Still, you should find almost every part you need at one of these stores.
Crafts and arts stores
Although these stores may seem "prissy" or "homemaker-like", there are many things you can get here that are less expensive than at a hobby store. You'll be amazed at what you find lying on their shelves.
Beit Home Depot, Lowes, or Menards, you can find most of your tools and hardware at relatively inexpensive prices.
Radio Shack is one of the major electronics stores around. You may find what you need at a store near you. If you can't find what you need, there are places like All Electronics and Electronic Goldmine that will contain a variety of different products you can use.
Question: I know what wood, metals, and plastics are, but how would I know what everything else is?
Answer: Well, let's start with one of the most common components of robots -- electronic components.