The auto-increment counter is stored only in main memory, not on disk.
Because of this when the service (or server) restarts the following will happen:
After a server startup, for the first insert into a table t, InnoDB
executes the equivalent of this statement: SELECT MAX(ai_col) FROM t
InnoDB increments by one the value retrieved by the statement and
assigns it to the column and to the auto-increment counter for the
table. If the table is empty, InnoDB uses the value 1.
So in plain English, after the MySQL service starts it has no idea what the auto-increment value for your table should be. So when you first insert a row, it finds the max value of the field that uses auto-increment, adds 1 to this value, and uses the resulting value. If there are no rows, it will start at 1.
This was a problem for us, as we were using the table and mysql's auto-increment feature to neatly manage IDs in a multi-threaded environment where users were getting re-directed to a third-party payment site. So we had to make sure the ID the third party got and sent back to us was unique and would stay that way (and of course there's the possibility the user would cancel the transaction after they had been redirected).
So we were creating a row, obtaining the generated auto-increment value, deleting the row to keep the table clean, and forwarding the value to the payment site. What we ended up doing to to fix the issue of the way InnoDB handles AI values was the following:
$query = "INSERT INTO transactions_counter () VALUES ();";
$transactionId = mysql_insert_id();
$previousId = $transactionId - 1;
$query = "DELETE FROM transactions_counter WHERE transactionId='$previousId';";
This always keeps the latest transactionId generated as a row in the table, without unnecessarily blowing up the table.
Hope that helps anyone else that might run into this.
As Finesse mentioned below it appears the behavior of this has been modified in MySQL 8.0+.
The wording in that worklog is faulty at best, however it appears InnoDB in those newer versions now support persistent autoinc values across reboots.