Dont even bother with MS Virtual PC. Its not worth the hassle.
Download VMware Server (its free) as its much better and actually works when you want it to.
http://www.vmware.com/products/server/
Then get (for example) the Ubuntu ISO and save it somewhere
Configure a new virtual machine and tell it to use the ISO to boot from and just install as normal.
Theres an option in the VMware menu to install VMware tools, some useful utilities that you might find helpful, but you can only install them once Linux is installed (obviously).