I've been asked a few times what to buy when starting with electronics, especially when it comes to micro-controllers and sensors. You're going to end up buying a ton of parts while exploring. You'll have a hard time using a lot of these components until you're comfortable with their conventions. It's also important to make sure your everything works together.
For starters, lets go with a kit - the SparkFun Inventors Kit.
It comes with a wonderful guide book and an ever-growing selection of parts, including an Arduino, motors, servos and a display. You can use these parts "as is", without soldering or buying more parts. The guide book covers programming the Arduino in C and has a bunch of example circuits. These circuits are also applicable if you wish to play with a framework like Johnny-Five or Artoo.
I also want to recommend Getting Started in Electronics. It's a wonderful book that's very approachable. It comes with 100 projects that you can do with the parts from the kit and household items. (Or with quick trips to RadioShack.) At the very least read the reviews. They are all along the lines of "this book changed my life". I could very well write one like that too. I can also recommend Forrest M. Mims III's other books, they are all many versions of amazing.
Adafruit and SparkFun are my goto sites for parts sourcing. Most of their parts are of good quality and they both have good instructional sites. Eventually you may find companies like Jameco and Mouser. They are parts wholesalers and usually have better prices, but it takes a lot of work to make sure you know what you're getting!
Feel free to ask me any questions, and keep hacking!
Since SparkFun has sold out of their inventors kit. I will also recommend the Adafruit ARDX - v1.3 Experimentation Kit for Arduino it's almost as good. I just wish it had a display.
Sparkfun has a new version of their kit back in stock!