Fedora has built in Xen support and thus, patched Xen kernels available. I am not too sure about Ubuntu in terms of installs but what you want shouldn't be a 'big deal' - make sure you have downloaded vnc viewer, if you don't already have it and then try virt-install (...if it is running on Ubuntu which it probably is!) If you don't have it you can get it at:
I strongly recommend using the latest version!
It will want to have you get Fedora off the 'net or over a network it does not accept disk based installs, right now.
...where the "..." is surf their pages to fill in the rest of the string to get the latest version Fedora 8.
Follow the interactive commands for virt-install and it will manage everything!