This is trickier than I thought before I was in the market for a box that can handle 64-bit guests.
Myth #1: All 64-bit hosts can run 64-bit guests. False. 64-bit guest requires specific hardware support: VT-x or AMD-V.
Myth #2: All 64-bit processors support 64-bit guests. False. See myth #1.
Myth #3: All current Intel 64-bit processors have VT-x. False. Many brand new 64-bit processors (T6400, T6500 etc.) do NOT support VT-x, in the name of market segmentation.
Myth #4: All machines with VT-x capable processor can support 64-bit guest. False. VT-x support is disabled by default on Intel processors and needs to be enabled by BIOS. Many BIOS, e.g., those in most Acer laptops, do NOT have the option to turn on VT-x.
Basically host OS is irrelevant w.r.t 64-bit guest. If you're looking for a cheap machine to run 64-bit guests, stick to current AMD Athlon 64 (with AM2 or AM3 sockets) or Opteron (2+ generations) processors, as AMD-V support is on by default.