I would suggest to start reading the datasheet on a a specific microcontroller. If you are using PIC, for sake of simplicity, i would recommend an 18F series, because the older PICs have something called bank switching, which can be a bit of pain.
You can get C18, which is microchips C compiler for the PIC18 series. The student one is free, but after 60 days, optimization is limited and you are bounded to a 2Kb program. If you are coming from a computer programming side, 2Kb may not seem like alot, but its pretty decent on an embedded scale.
To program, I would recommend getting some type of ICD2 or some clone of it. The reason is because if you are learning, there are going to be mistakes which you just cant understand and having an ICD2 would be helpful. I bought mine off ebay for $50, and it works fine. I believe there is something called a Junebug floating around here that is an ICD2 clone or something. Not to sure, but Im sure someone will post more info on that a little later.
To build your circuit, start off with something called a breadboard. Its pretty much a plug-and-play type deal. No solder required. This way, you have the ability to make changes until you are finally content with it, and then from there, either get a perf board or make your own pcb.