I am just starting out with LaTeX on Windows XP, and I was advised to install MiKTeX.
What would I get in the complete MiKTeX that isn't in basic MiKTeX?
The basic MiKTeX installs a small set of packages. The complete one installs all of the ones that MiKTeX knows about. As MiKTeX can install packages 'on the fly', the main advantages of the complete install are
If you are using your own PC and will be attached to the internet most of the time then you can happily use the basic installation and add packages 'as needed'.
A bit more detail on multi-user systems. MiKTeX will install packages for each user separately, which is fine for a couple of people using a small set of packages, but would be bad for a system used by lots of people with very varying requirements. Hence for network-type installations a 'full' install or at least a bigger set of packages than the 'basic' is usually preferable.