TL;DR
Add the following to .bashrc:
PS0="$PS0"'$(history -a)'
PROMPT_COMMAND+=( 'history -n' )
(as of bash 5.0)
Long answer
Saving history
Other answers use PROMPT_COMMAND, which only appends a command to the history file after the command is done running. Ideally we would like to write the command to file immediately after entering it. Bash 4.4 added PS0, which is interpreted before a command is executed:
New prompt string: PS0. Expanded and displayed by interactive shells reading a complete command but before executing it.
Source: CHANGES file in the Bash tarball.
Thus, we can extend PS0, being careful to literally append the string $(history -a) so that the execution of the history command is delayed until bash expands PS0.
PS0="$PS0"'$(history -a)'
Since history -a doesn't have any output, we shouldn't need to worry about its output becoming part of the prompt.
Loading history
On the other hand, loading history is still most useful immediately before we start entering a new command. However, note that as of Bash 5.0, PROMPT_COMMAND is intended as an array variable (although using it as a single string still works):
PROMPT_COMMAND: can now be an array variable, each element of which contain a command to be executed like a string PROMPT_COMMAND variable.
Source: same changelog.
Thus, the proper way to add a new command to it uses Bash's array syntax:
PROMPT_COMMAND+=( 'history -n' )