I hate to answer by not answering, but where do you want to start?
What interests you the most - construction, electronics, programming?
All of the above?
You can buy ready to run robots, you can buy kits, you can use Legos, you can build a robot from wood, plastic or cardboard... You can even hack RC vehicles.
For controllers - some kits come with one, you can use something like an Arduino, Raspberry pi, you can build your own using any number of micro controller chips.
Start by reading through the $50 robot tutorial on this site for a good example of a bottom line DIY approach. You could expand on that with better hardware and a more capable micro (I like the ATmega1284p for the most pins in a through hole package) or swap in an Arduino.
A search for robot kits will get you lots of choices from places like sparkfun, pololu, robot shop, etc.
Once you have some idea about what exists on the ends of the spectrum, then you can better decide where to jump in.