After finding how-to upon how-to that said to use "apt-get install ubuntu-xen-server" and repeatedly banging my head against the wall because it kept telling me the package wasnt found, I finally found the Xen page at the Ubuntu Community site that explained the situation. Apparently, there is no such package for amd64 kernels and you need to specify each needed package. Thankfully, they list the command you need over there:
(you do need to uncomment the universe repositories in /etc/apt/sources.list)
sudo aptitude install linux-image-xen bridge-utils libxen3.1 python-xen-3.1 xen-docs-3.1 xen-hypervisor-3.1 xen-ioemu-3.1 xen-tools xen-utils-3.1
Once you run that command, reboot the machine (may not be needed but won't hurt)
Now you'll need to edit /etc/xen/xend-config.sxp and uncomment the line (network-script network-bridge) and then comment (network-script network-dummy).
They also recommend adding "max_loop=64" to the end of the "loop" line in /etc/modules but this may not be needed for all people -- again, it won't hurt.
Now just reboot and it should all work.
NOTE: If your using i386, "apt-get install ubuntu-xen-server" should work for you. It's also possible that by the time you are reading this, the same command will work for amd64 but as of this post, it does not Reference Link