How do you make Git work with IntelliJ?

You need to specify the executable path of Git in the Git Settings, as mentionned in the per-requesites:

The Git integration plugin is enabled and the location of the Git executable file is correctly specified on the Git page of the Settings dialog box.

As long as you see “a message indicating that the Git execution path is not correct”, the rest of the instructions won’t work.

Path to Git executable

In this text box, specify the path to the Git executable file.
Type the path manually or click the Browse button to open the Select Path - Git Configuration dialog box and select the location of the Git executable file in the directories tree.

See “Where is git.exe located?” for the path of Git on Windows.

• with Git for Windows:

    C:\Program Files\Git\mingw64\bin
  

OR

    c:\path\to\PortableGit-2.6.2-64-bit\usr\bin

OR

    c:\path\to\PortableGit-2.x.\mingw64\bin

• With GitHub Desktop:

    %USERPROFILE%\AppData\Local\GitHub\PORTAB~1\bin\git.exe
  

Update 2020, three years later:

As noted by Daniel Connelly in the comments

IntelliJ now lets people install it through the path specified in the help above (just look for the “Download Now” button on the Git menu).
If you download Git from the website, a version that IntelliJ does not support will be installed.