In my experience there is an initial learning "hump", if you will, in embedded systems that can be tough to get over, but once you do you will be disappointed if the first project you choose is very simple.
There is some initial investment in the development tools (ie. the chips and the programmer at the very minimum). Building a very simple project will not let you explore the more useful areas of the chip, hence the amount of knowledge that you will obtain will be disproportionate to the amount of resources that you invest; both in time and money.
I suggest making something more engaging than a couple of blinking LED's. The hardest part of developing for a new embedded platform, for me, is always getting the initial compilation and uploading the first program to the chip. Since this step is the same no matter how complicated or easy your first project is, I would again vote strongly in favor of embarking on a moderately complicated project right away. Something like an IR remote control comes to mind. In any case expect to invest a lot of time if you truly want to learn anything.
I would also suggest NOT going for something like a BASIC STAMP or even Arduino, since these devices wouldn't teach you the true skills needed to do embedded programming. They are more of a platform that will run your high level code. You are using a glorified version of such a platform to read this post, your PC; hardly an embedded device. On the plus side, they will save you a lot of trouble if you are not familiar with electronics.
Get an 8-bit chip made by Microchip or ATMEL, both very popular and relatively cheap to start, get a programmer and perhaps a demo board, the demo board works if you are not familiar with electronics, for one of those chips. Most importantly, read the accompanying data sheets, and try to build something moderately useful. Program in C or assembler. ATMEL is much better with compilers and support for C. In the long run you will be glad you did not waste your time learning a platform that nobody in their right mind would use for a commercial product and you will gain a better understanding of dealing with the limitations of embedded systems, since there is no better source of information than the data sheet.