How do I tell mkdir to try creating dir1, and if it already exists create dir2, etc, until it hits a name that doesn't exist?

This is a trivial exercise in the use of while:

n=0
while ! mkdir dir$n
do
    n=$((n+1))
done

But of course it doesn't take much thought to realize that this trivial mechanism doesn't scale well.

So instead of reinventing the wheel and having to shave off all of the corners again, one creates unique temporary directories from a template slightly differently:

name=$(mktemp -d dirXXXXXXXXXXX)

If you just want to incrementally create directories that are listed in the correct order, may I instead recommend folders that are named based on the current date?

DATE=$(date +%F)
mkdir "dir-$DATE"

It will create directories with the names like dir-2014-03-02 (YYYY-MM-DD, so as to appear in alphabetical order).

If you create more than one directory per day, you can add the current time to the file name. See man date on how to tweak the output formatting of date.