Options:
a) Assuming the VM is Windows, yes, install Windows in Bootcamp. It's the only way to start Windows before any OS X user logs in. 
b) Use automatic login in OSX and add Parallels VM to the login items (it's not exactly what you want), not very secure, but suppresses the need for users to key in their credentials.
c) Not saying there's absolutely no way to run Parallels before login, but would likely involve heavy modifications, and in the end the Process has to be run by some user even if it's root, which would be dangerous, so use option b) instead.
Last edited: Jan 15, 2013