In the second, the app not only takes over the entire screen, but it also forms its own virtual desktop in Mission Control. (Apple's own apps go full-screen in this second sense.) If you look in Mission Control when you're running Fusion, you'll see that each Windows application appears on its own, just like any OS X application. With Parallels, all of those separate app windows are lumped together with the Parallels icon. (If you open the Command-Tab task-switcher, though, you'll see separate entries for each Windows app in both Fusion and Parallels.)
Fusion and Parallels use a mix of these two full-screen modes, depending on which OS you're virtualizing and the number of monitors you have connected to your Mac.
If you run an OS X virtual machine on a single screen in Parallels, it'll fill that one screen but won't get a desktop of its own in Mission Control. But if you run Linux in the same mode, it will. Run a Windows virtual machine under those same conditions, and you can choose (via a toggle in the virtual machine's options screen) which mode it will use. Fusion makes the single-display scenario simple: You get OS X's true full-screen mode, complete with its own Mission Control desktop, for OS X, Linux, and Windows.
When you hook up more than one display, both programs let you toggle between using all of those displays in full-screen mode or just one. If you set Fusion to use all displays then run Linux or Windows, the virtual OSes will take over all of the screens and create their own desktops in Mission Control; OS X uses up just one. Parallels handles Linux and OS X the same way; if you're running Windows, you can choose to run it in true OS X full-screen mode (a Mission Control desktop is created) or just have it fill all of the displays.
In Linux particularly, Parallels handled the multiple screens poorly: It used only two of my three in full-screen mode, and those two appeared as one ultra-wide display. Fusion used all three, and each was treated as a separate screen.
Despite these disparities, both programs actually handle full-screen modes better than Apple's own apps when you have more than one display. Those apps fill one screen and leave the rest blank. Fusion even offers a cool mini toolbar (when running Windows) that lets you drag the full-screen window to any of your other displays.
Both apps also now work with Notification Center. Fusion will use it to send Fusion-related messages, such as a notification of an available update. Parallels goes farther: It'll notify you about updates too, but also when you do things such as sending special keystrokes to a Windows virtual machine.