Are you looking specifically at embedded software development, or are you interested in circuit board design as well?
If it's just software, then I would suggest getting hold of an ARM development board (Possibly the Philips LPC range - sparkfun have some nice ones) that you can program via a bootloader over usb and start hacking. Get one with a display and an ethernet port and you can build up to making some sort of network attached sensor (temperature, water level, object counter, etc). Start out little (turn on a LED from a button) and work your way up.
If you're also into the electronics side of things, I'd suggest something like an MP3 (or WAV) player and maybe stick to the AVR or PIC 8bit microcontrollers (AVR is used on the Arduino) as these are a little easier to deal with than ARM. Here you could start with a usb powered device that streams wav files from a PC serial port out to a pair of headphones, and build up to a battery powered board, feeding data to an MP3 decoder IC from an SD card.
Some things you may want to learn & demonstrate:
- Understands the bounds of working with limited resources, including memory management (dynamic and/or static); resource management (locks, semaphores, mutex); multiple tasks (interrupts); and appropriate data structures
- Ability to interface with other devices/ICs over various interconnects (analog & digital IO, serial bus (RS232, I2C, SPI))
- Ability to sanely structure a program and segment the various modules without producing 'spaghetti' code
- Ability to use source and integrate 3rd party libraries where appropriate (think FAT filesystem, or TCP/IP stack)
Misc Tips:
- read and understand the datasheets (yes all of them)
- code and test on the desktop where possible, but understand that there are differences and bugs will still creep through (this is where it helps to be using a tool-chain that is common with the desktop - GCC is good, but the tools are generally CLI)
- use assert a lot - you can flash the line number of a failed assert using a single LED - this is invaluable
Most of all have fun - it still makes me smile when you first get a new component working (display, motor, sensor). Embedded makes the world go round :)