Certainly start with the first item on Golem's reading list, and then read anything and everything you can find on the web about robotic projects at a suitably introductory level. You will find that common themes start to emerge and you will gain an overview that will help a lot - when you have a problem you will have some points of reference and some idea of what it is you need to find out.
Secondly, previous advice notwithstanding, I'm going to suggest that you do start with Picaxe. It will be a good while before you outgrow it and it's not expensive. Initially you will want lots of information, and one of the good things about Picaxe is that there are very good (free) manuals on the Picaxe website covering the system as a whole, the programming language in detail, and how to interface the controllers with external circuitry. Having all that information in one place, and specific to the system you are using, will save you many hours of searching and frustration. There is also a helpful forum where you can go for advice when you get stuck, or just want to know the best way to do something.
Any microcontroller needs a certain amount of support circuitry to make it work and enable you to program it. To keep things simple you could buy a Picaxe-28X2 Module - it's a little more expensive, but it comes with the support circuitry (voltage regulator, resonator, programming interface and reset switch) already built in. It's about as close to plug'n'play as a microcontroller gets. You will need:
The microcontroller module
Programming software (free download from the website)
A download cable - probably USB if you'll be using a laptop
A breadboard (eBay)
Some assorted jumper wires (eBay)
A couple of LEDs, a couple of 330 ohm resistors and a sounder (Picaxe website)
That should be plenty to get you started. Long ago as it was, I still remember the buzz from seeing my first microntroller program flash an LED. When you've mastered flashing and beeping, you might decide you'd like to try a mobile robot - there are plenty of expensive robot chassis about, but there are also some reasonably cheap ones (under £20), such as this one from HobbyTronics.
(I have used several kinds of controllers in my own projects, including Picaxe. Picaxe was my system of choice for teaching introductory control systems to students in a college of further education. There are a couple of Picaxe projects on my website, which is sorely in need of updating.)