How to start embedded Programming?
I still think programming on "bare metal" is the best way to get involved in the embedded world.  IMHO, running on top of a platform like Android doesn't give you a real taste of embedded programming.

Although there are a lot of 8-bit microcontrollers out there, the future is 32-bit.  I happen to like the PIC32 series from Microchip.  You can get a complete development board from SparkFun for $40.  You don't need to buy anything else to start with, since there is a bootloader built-in.  You can also use one of Microchip's programmers like the PICKit 3.



This board uses the popular PIC32MX795, which has 512K flash and 128K of RAM, so you won't be outgrowing it any time soon.  There are tons of free libraries to make programming the peripherals easier.

Microchip has a free IDE and compiler that runs on Windows, Linux, and Macs.  (They also have a paid version, but all that gives you is optimzations to produce smaller code.  You don't need that for hobbyist use.)