Repairing the GRUB bootloader

When you install Windows, Windows assumes it is the only operating system (OS) on the machine, or at least it does not account for Linux. So it replaces GRUB with its own boot loader. What you have to do is replace the Windows boot loader with GRUB. I've seen various instructions for replacing GRUB by mucking around with GRUB commands or some such, but to me the easiest way is to simply chroot into your install and run update-grub. chroot is great because it allows you to work on your actual install, instead of trying to redirect things here and there. It is really clean.

Boot from the live CD or live USB, in "Try Ubuntu" mode.

Determine the partition number of your main partition. sudo fdisk -l, sudo blkid or GParted (which should already be installed, by default, on the live session) can help you here. I'm going to assume in this answer that it's /dev/sda2, but make sure you use the correct partition number for your system!

If your main partition is in an LVM, the device will instead be located in /dev/mapper/, most likely, /dev/mapper/{volume}--{os}-root where {volume} is the LVM volume name and {os} is the operating system. Execute ls /dev/mapper for the exact name.

Mount your partition:

sudo mount /dev/sda2 /mnt #Replace sda2 with the partition from step 2

If you have a separate /boot, /var or /usr partitions, repeat steps 2 and 3 to mount these partitions to /mnt/boot, /mnt/var and /mnt/usr respectively. For example,

sudo mount /dev/sdXW /mnt/boot
sudo mount /dev/sdXY /mnt/var
sudo mount /dev/sdXZ /mnt/usr

replacing sdXW, sdXY, and sdXZ with the respective partition numbers.

Bind mount some other necessary stuff:

for i in /sys /proc /run /dev; do sudo mount --bind "$i" "/mnt$i"; done

If Ubuntu is installed in EFI mode (see this answer if you're unsure), use sudo fdisk -l | grep -i efi or GParted to find your EFI partition. It will have a label of EFI. Mount this partition, replacing sdXY with the actual partition number for your system:

sudo mount /dev/sdXY /mnt/boot/efi

chroot into your Ubuntu install:

sudo chroot /mnt

At this point, you're in your install, not the live session, and running as root. Update grub:

update-grub

If you get errors or if going up to step 7 didn't fix your problem, go to step 8. (Otherwise, it is optional.)

Depending on your situation, you might have to reinstall grub:

grub-install /dev/sda
update-grub # In order to find and add windows to grub menu.

If Ubuntu is installed in EFI mode, and EFI partition UUID has changed, you may need to update it in /etc/fstab. Compare it:

blkid | grep -i efi
grep -i efi /etc/fstab

If current EFI partition UUID (from blkid) differs from the one in /etc/fstab, update /etc/fstab with current UUID.

If everything worked without errors, then you're all set:

exit
sudo reboot

At this point, you should be able to boot normally.

If you cannot boot normally, and didn't do step 8 because there were no error messages, try again with step 8.

Sometimes giving GRUB2 the correct configuration for your partitions is not enough, and you must actually install it (or reinstall it) to the Master Boot Record, which step 8 does. Experience helping users in chat has shown that step 8 is sometimes necessary even when no error messages are shown.