You need the Arduino IDE, the editor in which you'll write your sketches.
You need the microcontroller board. There are many form factors to choose from. I have an Arduino Uno, and that's a great default choice. You might want one with additional capabilities, such as Ethernet or the extra processing power of the Mega, or you might enjoy the LilyPad, designed for being incorporated into costumes and wearables.
Note that a "shield" is a thing that plugs into an Arduino, so it doesn't have any brains on its own. Feel free to pick up some shields, they're a hoot, but be aware that you still also need an Arduino board.
Sources to buy from: AdaFruit Industries, Sparkfun Electronics, Maker Shed, RadioShack.
The slides from my talk are on SlideShare, and the sketch for the robot is on GitHub (along with a number of other sketches).
Pictures of building the robot, the video game, my ambient clock, and the thing under your bed.
What are you going to make? Leave a comment here or send me a note on Twitter (@scichelli). I can't wait to hear about it!