If you want Ubuntu on the same disk as Windows 8.1, here are the steps to go through:
1) [Turn off Windows Fast Boot]
2) You need to shrink the main Windows 8.1 partition. This can be tricky, as Windows expects a certain partition scheme to be used. Let me show you a diagram:
[(Windows RE Tools)(EFI System Partition)(Microsoft Reserved Partition)(Windows 8.1)(Anything else)]
You can use your favorite tool to edit these partitions. I prefer Gparted, but any good disk partitioning tool can handle this. Backup your Windows install first. Then, resize the Windows 8.1 partition so that you have enough space for another OS. I prefer to give my Linux installs about 50-100 GB of space (for expandability).
3) Download your Ubuntu (use 64 bit only and I suggest 13.10) iso and put it on some media (CD/DVD/USB/(insert your preferred media here)) by using your favorite tool (most people prefer Rufus) or dd. There is an alternative option to this(see *).
4) Shut off Secure Boot and Fast Boot in the UEFI. DO NOT TURN ON LEGACY BOOTING (if your motherboard supports UEFI only booting without Secure Boot and Fast Boot on.)
5) Insert your install media and install Ubuntu in the partition you made earlier. Make sure that for your EFI boot partition, you make the installer use the EFI System Partition already created by Windows 8.1. The partition should be something like sdXn (replace X with the drive it is on and n with the partition number, such as /dev/sda2), but this could be different. DO NOT REFORMAT THIS PARTITION!! You are only going to tell the installer to use it as the EFI partition. It will put the grubx64.efi bootloader for Ubuntu in this location.
6) With that done, continue the install as normal and set up your partitions as you see fit. Once the install is finished, you should be able to boot into Jessie easily.
If you are trying to fix an existing install of Ubuntu, you will need to do:
sudo apt-get install grub-efi-amd64
sudo modprobe efivars
sudo grub-install /dev/sdx (x being the drive Ubuntu is installed on)
From there, the UEFI should use Grub-EFI as the bootloader. I have not found a way to get the Windows 8 bootloader to see and allow Linux to boot in UEFI. YYMV.
*Note: If you want to not go through the hassle of Rufus or dd, I have had limited success following this procedure.
1) Make the UFD into a GPT disk. You can do this using diskpart in Windows (sometimes) or using Gparted in Linux (99% of the time).
2) Format the disk to FAT32.
3) Download your iso.
4) Extract the iso onto the UFD. Make SURE it has an EFI folder in the root partition of the drive.
5) Once the contents are extracted, take the disk back into Gparted. On the partition, right click and bring up the Manage Flags dialog. Click check the
boot box. There is also a way to do this in diskpart, but it requires setting the id of the disk, which is just a pain.
6) This disk should now be UEFI bootable. Follow the rest of the guide from where the asterisk was to the end. Caveat, since this is on a laptop, there should be a mode that has
UEFI with CSM which shuts off Secure Boot and Fast boot and will still allow the D-I to install in UEFI mode. Pray your laptop has the option to disable Secure Boot without doing this.