Cleaning out the ~/Documents/Parallels folder (which, by default has the VMs stored) and then running the Parallels uninstaller should more or less do the job. Of course, if you want to just remove a VM, you can do that while running Parallels, provided the said VM isn't active.