I have some experience in this field, coming from a Forensics course and ending up in a CERT team. There are many resources for getting started with Reverse Engineering, but the main thing I can recommend is simply experimenting with live samples in VMs (There is a lot of research around VM escape at the moment). Using tools such as Sysinternals Suite \ Wireshark etc to capture what the malware is doing at a high level first of all, that can then guide your investigation into the actual code of the binary itself.
Lenny Zeltser (previously mentioned) has released a free VM specially designed for RE samples, entitled Remnux http//
There are several places online where you can pick up samples, or search your junk mail folder for obvious scams and use wget on the url and grab yourself one from the wild ;).
Also I can recommend the previously two mentioned titles "Malware Analysts Cookbook" and "Practical Malware Analysis" The cookbook can be quite heavy handed at times but its worth sticking with it.