So, this is all my history-related .bashrc thing:
export HISTCONTROL=ignoredups:erasedups # no duplicate entries
export HISTSIZE=100000 # big big history
export HISTFILESIZE=100000 # big big history
shopt -s histappend # append to history, don't overwrite it
# Save and reload the history after each command finishes
export PROMPT_COMMAND="history -a; history -c; history -r; $PROMPT_COMMAND"
Tested with bash 3.2.17 on Mac OS X 10.5, bash 4.1.7 on 10.6.
edit: updated with history -c from lesmana's answer, which you should checkout too.