Make sure your Mac BIOS allows 64-bit virtualization, and that Parallels is set to run x64 virtual machines (I can add some screenshots later on today).
EDIT: OK, I'm running Parallels 9 in a MBP Mid '10 and OS X 10.9.4. The technical article in Apple (Intel-based Macs: Using VT-x virtualization technology) does not apply to my computer (that is 4 years old). It seems that VT is enabled by default, so no screenshot possible.
However, make sure you have installed a Windows OS x64 as a guest OS, a screenshot of the System Info dialog will do.
Finally, if you are running OS X Lion 10.7 or older, the OS boots in 32 bits mode. It was not until Mountain Lion 10.8 when Apple discarded the 32 bit mode in the kernel boot.
In case of doubt, to check whether you are running your OS in 64 bit mode, go to the Spotlight, open Terminal and enter "uname -m". If it returns "i386" your computer is running in 32 bit mode and you should try enabling the 64 bit mode (OS X: Starting up with the 32-bit or 64-bit kernel), while if it returns "x86_64" then you are good to go.