The available answers miss one very big point which I'll try to somewhat address. The point is why do you want to learn how to program microcontrollers.
The problem with "just learning" how to program microcontrollers is that microcontrollers themselves are a very wide field and that some of the acquired knowledge may not translate well to another platform.
So basically you have several "grades" of microcontrollers and each grade has its own specifics and available platforms.
The simplest would be the beginner hobby grade in which the Arduino is the most popular system. In addition to what others have said there are few more things which need to be taken into account in this grade. First is that the boards themselves are expensive (some would say inexpensive, but read on) and they themselves don't provide too much. Their main promise is that with a simple board, USB cable, wall wart and few wires you'll be able to make an interesting project. This is somewhat true, but the points which are often missed are the need for so called "shields" and consumption of Arduinos themselves. There's no easy way to use Arduino in a complete permanent project without "using up" the board or moving to the next grade. Other similar systems such as PICAXE suffer from same limitations. So basically their good side is that you'll be able to "touch the water with your toes" and be able to do so cheaply, but the bad side is that they hide the actual microcontroller programming from you and that they're easy to outgrow. Also it is taken for granted that the price of the system isn't a problem and can be afforded. For these reasons, they're very rarely used for any professional work. Another point which is important but becomes visible only after moving to a higher level is that the core part of Arduino is the bootloader which allows the microcontroller to program itself therefore saving money on an external programmer.
Next grade would be something I'd call pre-Arduino hobby level. I decided to call it like that because it represents the entry knowledge which people needed to have before Arduino and similar platforms showed up. So the greatest difference is that you're using an 8-bit microcontroller itself directly and that all of its capabilities are exposed. The bad side of that is that you'll need a board which can host the microcontroller or you'll need to learn how make one yourself. There are numerous difficulties associated with making a board for yourself, even if it's made on a simple breadboard. You'll have to read microcontroller datasheets, understand what datasheets say, understand what they don't say and where to find that, understand what you think they say but in fact they don't or you think they don't but in fact they do... This at first may be complicated, especially when you open up datasheet for say AVR ATmega16 and see that the datasheet is 300+ pages long, written in a condensed style with each line being very important. Of course, not all of that is needed to start, but finding out what's needed is a skill that needs to be learned too. Next there's the financial part of the equation. An officially blessed programmer for say AVR or PIC can be in the range of 2 or 3 Arduinos. Of course, there are many third party programmers which can work too, but they may have their limitations such as only working quickly from a real RS-232 port and having extremely low performance with USB to RS-232 cables or not supporting latest chips and so on. Another thing that may be problematic is getting burned by old literature. Microcontrollers change over time and a book written several years ago may be out of date and recommend old chips which may be obsolete or out of production.
This all may be a bit difficult to digest but is necessary if you ever plan to write programs for microcontrollers in a professional setting or do any complex programming. The main good side of focusing on this approach is that once you digest the basics, you'll be able to easily and cheaply make your own boards for whatever project you may have in mind. As I said, you'll have to spend money or effort to get a good programmer and a starting board, plus some effort to learn how to use the standard IDE for the microcontroller you chose to use. A real bench power supply may be interesting to get and you'll have to learn how to solder (if you plan to move on from breadboards), get a multimeter, learn where to buy electronic components, but once you cross this stage, you'll be able to stand on your own feet, be able to understand what you have made and how to actually maintain it. In this stage, most popular microcontrollers are 8-bit AVRs and PICs. There are also other microcontrollers like for example Parallax Propeller (which has 8 cores!) or the MSP430. It's also worth noting that PICkit programmers can do debugging too while AVR programmers can only program and separate in-circuit emulator is needed to actually debug the running microcontroller. At this point, the basic setup costs, but cost of a project itself can be very low and can easily beat cost of a dedicated Arduino.
Next there's the the grade for devices which are on the edge of another field. This is for devices which are on the border of a microcontroller and a system on a chip or microcontroller and a digital signal processor and so on. This grade is somewhat more beginner friendly but is more complex than the previous grade. Devices here may share setup equipment with devices from the previous level which can make transition a bit easier. For example PICkit can work with 8-bit, 16-bit, 32-bit PICs and the 16-bit dsPIC digital signal processors. Devices themselves may or may not be available in easy to use formats, but even for hard to use surface mount packages, adapters into through-hole aren't rare and third party development boards are available too. In addition to devices already mentioned from Atmel and Microchip, at this stage various ARM-based microcontrollers become available. They're mainly interesting because they're very close to "real computers" and are often found in mobile phones. Development of home-brewed boards at this level gets difficult and pre-fabricated ones cost hundreds of dollars. On the other hand, you can expect to have say two cores, embedded Ethernet, ability to produce high quality video and so on.
Next level is what I'd call the budget level microcontrollers. We're still in the 8-bit land, but the cost of the device starts to be the main driving factor and the cost of the setup itself isn't too important. This is mostly of interest to people who are going to spend most of their time professionally writing code for devices which will be produces in large quantities. I don't have too much experience with this area, so I won't comment much on it, but most major semiconductor manufacturers have their own line of microcontrollers and their own proprietary development software and hardware which can get expensive. Chips themselves won't be in a form factor which is easy for prototyping, so you'll need to either get a evaluation board or make your own PCB to house the microcontroller. They also won't be available form the local friendly electronics store and instead will have to be ordered from major distributors which may have minimum order amounts (which may range from hundreds to thousands of units). So my advice would be not to go into this area until you need to do so.
I'd write more, but it's 02:35 here right now and I've noticed that I need to use spellchecker to correct each
work word I type, so that's it from me for now.