Is there a configuration option to [imply -u when the branch gets created by git push]?
There probably should be, but there isn't.  You can, however, fix things up afterward using git branch --set-upstream-to, just as in the Git error message.
As in the other answers, you can set up some alias(es).  To expand a bit on fracz's answer, it is safe use the -u option every time: this will set the upstream on every push, but assuming you are always pushing to the same place, you will "change" the upstream from origin/branch to origin/branch each time, i.e., not actually change anything.
Except for the progress output, there's not even a way to tell whether git push actually created the branch on the remote.  (The push command itself can tell, but it only reports this as that message, [new branch] or not [new branch].)  You can get fairly close by running git ls-remote before the push, but there is a race here: if ls-remote reports that the branch did not exist, and the push succeeds, you don't know for sure that your push created it, because there's a very slight possibility that someone else created it, but your push succeeded anyway.
It is, however, easy to tell whether there is an upstream before your git push started.
Here's a (somewhat imperfect and totally untested) script that does what I think git push should probably actually do.
#! /bin/sh
#
# Push, and set upstream if the push succeeds and
# there was no upstream set before the push started,
# based on "push.set-upstream" setting
die() {
    printf "%s\n" "$1" 1>&2
    exit 1
}
get_current_branch() {
    git symbolic-ref -q --short HEAD ||
        die "fatal: not currently on a branch"
}
get_remote() {
    git config --get branch."$1".remote || echo origin
}
upstream_is_set() {
    git rev-parse -q --verify "$1@{u}" >/dev/null 2>&1
}
# arguments are: [remote [branch]]
# we do not accept arbitrary refspecs here!
case $# in
0)  branch=$(get_current_branch) || exit $?
    remote=$(get_remote "$branch")
    ;;
1)  remote="$1"
    branch=$(get_current_branch) || exit $?
    ;;
2)  remote="$1" branch="$2";; # should check $2 ref format?
*)  die "usage: gitpush [remote [branch]]";;
esac
how_to_set=$(git config --get push.set-upstream || echo auto)
case "$how_to_set" in
always|true) do_set=true;;
false) do_set=false;;
auto|only-if-unset) if upstream-is-set "$branch"; then
        do_set=false
    else
        do_set=true
    fi;;
*) die "fatal: don't understand push.set-upstream=$how_to_set";;
esac
# figured everything out, so now push; fail if push fails
git push "$remote" "$branch" || exit $?
# last, set upstream if still needed
if $do_set; then git branch --set-upstream-to "$remote/$branch"; fi