VirtualBox is a wonderful app. I love it. You should be aware that any virtual machine is going to be touchy about kernel upgrades tough, so read the ubuntu forums for suggestions to keep them running well. Also, if you want USB support, I think you still have to use the "closed source" (but still free) version available at the VirtualBox website (http://www.virtualbox.org/
Wine is a much smaller solution, but it can be a little touchy to set up PAF. It's very important to use the "all languages" version and install the unicode font or your interface will be all kinds of funky. It's bigger than the "english only" version, but not enough to really worry about.
Here's the steps I used to make my PAF install work in Wine:
1) Enable the extra repositories
2) Install Wine
3) Download the PAF executable from: http://ftp.ldscatalog.com/PAF5AllLangs.exe
(it's also hidden on the PAF install disk, if you have one)
4) Start the PAF installer using Wine
5) Wine will probably allow the installer to indicate the default installation directory:
The instructions I have are a year old, but said to change the install directory to:
"z:\home\[username]\.wine\drive_c\Program Files\FamilySearch\Paf5\..." (I don't know why)
6) During installation, check the "International Unicode Font" checkbox
If you have several Windows apps that you want to use though, I'd lean toward VirtualBox; it takes a little education, but it's well worth it. And like Tom said: it's faster for me to run Windows as a VM than it is to run it as a native OS.