Beware: The instructions are for clean installing an OS. That means ALL YOUR DATA will be permanently LOST. If your phone was previously rooted it will be brought back to an unrooted state (whether you want it or not).
Please, remember to make backups of any important data on your phone. It will be lost.
1. Turning on USB debuging
Turn on USB debugging on your device:
Go to System settings / Developer options and check "USB debugging".
You will need the fastboot tool. It's an official Google command line tool intended for developers. You can follow the official instructions for installing the tool, but they are pretty complicated. If you are on Mac OS X or Linux you should probably do what I've done and use the adb-fastboot-install open source tool.
Just download it, unzip it and use one of the following command line instructions (depending on your operating system):
Obviously while doing that you need to be inside the directory containing those files.
There are plenty of instructions on how to install fastboot on Windows (for example this one). See also user17512's answer for an alternative method for Windows users.
3. Going to device's fastboot mode
You need to connect the device to your computer using a USB cable and then access your device's fastboot mode:
On Nexus S: Turn off your phone. Press and hold Volume Up,
then press and hold Power.
On Galaxy Nexus, Nexus 5 and Nexus 10: Turn off your phone. Press and hold both
Volume Up and Volume Down, then press and hold Power.
On Nexus 4, Nexus 6, Nexus 7 and Nexus 9: Turn off your device. Press and hold Volume
Down, then press and hold Power.
4. Unlocking the bootloader
Execute the following command on your computer:
fastboot oem unlock
Note: this step will remove all your data from the device.
5. Downloading the factory image
Download the factory image for your particular device and your desired Android version directly from Google.
6. Installing the system
Unpack the archive (if you are on Windows you will probably need to download additional software for unpacking .tar.gz files. 7-zip will do the job. Mac and Linux users have all the required software installed already).
Go inside the newly unarchived directory and execute the following command:
Note: This will wipe all data from your device
After some time your device should reboot and boot to your newly installed operating system :)
7. Relocking your bootloader
This step is not strictly necessary, but it's a good idea for security reasons. Reboot to the fastboot mode again (see step 2 above) and execute the following command on your computer:
fastboot oem lock
This worked great for me, I hope it will be helpful to other people :)