I used both several versions ago and here's my $.02
I found parallels to be ok, but a bit unstable in the early versions. The company also over promised on a number of topics and under delivered on them. To compound matters their support was lacking and the problems were very frustrating. My personal problems were such that parallels caused numerous Kernel Panics.
As for VMware, they did not over promise but delivered a solid product that was extremely stable and they continued to update it. to that end, I've been a VMware user, the downside (if you want to call it a downside) is that parallels maybe better now, but since I stick with VMware, I have no idea.
Finally VMware has a long track record of producing exceptional products, not just fusion, and standing behind them. That's one of the main reasons why I went and stayed with them.
I'm sure at this point parallels is a stable application, but since I've not used it since version 3 I'll let others chime in on version 4.
I've used VirtualBox on OSX and I currently use if on Ubuntu. On OSX I found it not as polished as VMware, lack of integration and the performance was such that I quickly deleted the application. I found quite the inverse on Ubuntu, its a more rounded and polished product and I use that when the need arises and as the other poster mentioned - its free
