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.
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 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:
After completing the installation you can launch it from System->Administration->Boot-Repair menu if you use Gnome, or search "boot-repair" in the dash if you use Unity. Then follow the following screenshots:
On EFI-based systems (such as most systems that shipped with Windows 8 or later), Windows will sometimes update its boot loader or reset it to be the default boot loader. This is particularly common when re-installing the OS or performing a major system update (upgrading to the latest Windows release, for instance). Note that Windows is unlikely to actually erase any GRUB files on an EFI-based computer. Everything needed to boot Ubuntu is still in place; it's just being bypassed. In these cases, a complete re-installation of GRUB is overkill, and in fact that carries a (small) chance that it will create new problems.
There are other variants on these procedures, such as using bcfg in an EFI shell, using bless in macOS, using my rEFInd to do a one-time boot, etc. I'd start with EasyUEFI, though; it's likely to be the simplest solution. Sometimes Windows insists on making itself the default every time it starts up, though, and reports indicate that bcdedit may do a better job of dealing with that problem.
Note that none of the preceding applies to BIOS-mode installations; however, as most computers that shipped with Windows 8 or later boot in EFI mode, BIOS-mode installations are becoming increasingly rare, so in many cases it's better to deal with the issue in the EFI way rather than by blindly re-installing GRUB.
All the available repair options are described in the Ubuntu documentation and there is a separate page explaining how to start Boot-Repair (by creating a bootable disk or installing it in an existing Ubuntu live disk) and how to use it.
There are many possible causes to a GRUB break: Windows writing on the MBR, DRM preventing GRUB from installing correctly, installer bug, hardware change...Updating GRUB as proposed initially by Scott is generally not sufficient, reinstalling GRUB as proposed by Marco is more efficient, but still there are various situations requiring other tweaks (adding options to kernel, unhiding GRUB menu, changing GRUB options, choosing the right host architecture...).Other difficulties for repairing GRUB is the use of chroot, and the choice of the right partitions /disks.
All of this has been made easy in a little graphical tool: Boot-Repair. Itshall be integrated in Ubuntu 12.04 CD for easier use, but for people needing it now, there are already some distros integrating it: Ubuntu-Secured-Remix (Ubuntu CD integrating Boot-Repair), Boot-Repair-Disk (CD running Boot-Repair at start-up), ...
Answers given by Scott and Web-E are good enough and have helped a lot many times. But many a times, the boot-repair tool is not able to repair grub due to problems related to i386 and amd64 platform or one where grub can't find efi directory.
What has solved my problem like more than 10 times is to manually purge the old grub installations and install a new one.
If Ubuntu is installed in EFI mode ([see this answer if you're unsure][efi]), 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:
Scott Severance's answer is valid and detailed but there is a resolution that requires no external boot device and so no need to identify and manually mount all of your Ubuntu partitions leading up to the chroot.
Some have had issues if the new primary partition is after the extended partition as Windows does not always reset partition table correctly. Best to have good backups and a separate backup of partition table.
As pointed out by @karels comment, the grub config is generated using the files in /etc/grub.d. My directory only contained /etc/grub.d/25_custom, which contained strange menu entries pointing to non-existent .efi images. It looked like my /etc/grub.d templates were maybe hosed by boot-repair.
795a8134c1