What is the best way to get started?
The starter kit would get you everything you need to do a whole set of projects. Alternatively there is a PDF on the Arduino site with a whole set of projects in it. You could go through it, put together an inventory of the parts you need, and order those parts from an electronics supplier like Mouser, DigiKey, Jameco, etc, and save some money. 

The starter kit is probably worth the extra money, though, because it has everything you need, plus an organized set of lessons that teach you the various skills you'll need.