So I found this really useful tutorial on skinning, or as the term in Maya is used "Binding", and I thought it'd be nice to share with everyone.
PLEASE PLEASE PLEAAAASE ignore the terrible American accent. He actually makes my brain ache. Although, the tutorial is very good to follow through. I'm going to be writing up my own tutorial, hopefully simplified too.
Skinning/Binding in Maya