Spice support has been present in Fedora for 2 releases now. Prior to that it was possible to use it on Fedora and Ubuntu if you were willing to install and build a couple packages from third parties.
Currently you can use it most easily if you are using Fedora 16 and install the virt-manager stuff. That should now have spice support integrated. So after you install VM you can go into the details view and convert the video to spice and the vga card to 'qxl'. After that a reboot should do it.
The video drivers necessary on the client side (qxl device) have been available in every distro for a couple releases now, I believe. If not then you can use a vga or vesa device with spice and it will work well, just not as well.
This Boxes release seems like a attempt to finally have a desktop friendly solution for KVM. Which is needed. Kudos to Gnome folks for the attempt.