Embedded Linux start, Help
There are some steps before getting on embedded linux. As @KKToronto said, it would be nice if you have a desktop linux experience first. If you don't have any experience I recommend installing Ubuntu in your desktop/notebook in order to get some feeling with the OS.

To go from the desktop to the embedded world, at least on linux way, is relatively easy, if you're planing to develop FOR embedded linux. Almost all drivers interfaces, kernel calls, are the same. One program that runs on a desktop linux, can run on a embedded linux with minor alterations. The beagleboard platform is a good example, as @JobyTaffey noted. Some applications I developed can run on both desktop and the beagleboard without code alterations, just need to use the correct compiler.

Still on the "develop for embedded linux" topic: one of the main alterations is the compiler, mainly because almost all embedded processors that are powerful enough to run linux are ARM ones. From the C/C++/Java programmer it is almost like migrating from x86 to ia64.

If you want to get a deeper "embedded" experience as building device drivers for new hardware, accessing I/O ports on the board, control external equipments using linux, I'd go with Linux Embedded Primer. It is a great book to learn on low level stuff as how the device drivers are made, how to get access to fixed memory locations that represent some peripheral etc. (And it has an amazing lightsaber on the cover =) )

By going on the hardware side a deep microcontroller knowledge is really important, because you're going to be dealing directly with memory for peripheral configuration/access. Some operations may even require assembly knowledge, mainly interruptions or flash writing. It depends a lot on the microcontroller architecture.

If you have no experience on this, I'd recommend to start with arduino, as @stevegt noted, to get a hardware/electronics feeling and then proceed to a baremetal programming over any other processor, to learn some tricks related to hardware/software interface, that are somehow hidden on the arduino firmware or linux kernel.

As you can see that is much knowledge hidden on "embedded linux" expression. Keep in mind that you don't need to have all of it to build an embedded system. You need to focus on what side you want to learn first and get a pre-made system for the other: arduino for hardware first contact, beagleboard to learn programming for embedded linux, a baremetal processor for hardware/software interface.

Specifically for your case I'd recommend the beagle board. As you have some programming and microcontroller background, you can develop some applications in high level to get experience at linux programming and when you fell comfortable enough you could start hardware stuff with the available I/O's on the board.