I have been spending a lot of time in the shell lately and I'm wondering how the tab autocomplete works. What's the mechanism behind it? How does the bash know the contents of every directory?
There are two parts to the autocompletion:
The readline library, as already mentioned by fixje, manages the command line editing, and calls back to bash when tab is pressed, to enable completion. Bash then gives (see next point) a list of possible completions, and readline inserts as much characters as are identified unambiguously by the characters already typed in. (You can configure the readline library quite much, see the section Readline init file of the Bash manual for details.)
Bash itself has the built-in complete to define a completion mechanism for individual commands. If for the current command nothing is defined, it used completion by file name (using opendir/readdir, as Ignacio said).
The part to define your own completions is described in the section Programmable Completion. In short, with
complete «options» «command» you define the completion for some command. For example complete -u su says
when completing an argument for the su command, search for users of the current system.
If this is more complicated than the
normal options can cover (e.g. different completions depending on argument index, or depending on previous arguments),
you can use -F function, which will then invoke a shell function to generate the list of possible completions.
(This is used for example for the git completion, which is very complicated, depending on subcommand and sometimes
on options given, and using sometimes names of branches (which are nothing bash knows about).
You can list the existing completions defined in your current bash environment using simply complete, to have an impression on what is possible. If you have the bash-completion package installed (or however it is named on your system), completions for a lot of commands are installed, and as Wrikken said, /etc/bash_completion contains a bash script which is then often executed at shell startup to configure this. Additional custom completion scripts may be placed in /etc/bash_completion.d; those are all sourced from /etc/bash_completion.