On shared web hosting, are all subdomains like
bar.example.com always hosted on the same server (same IP address)?
They typically are. They're usually subdirectories within the root web directory or one level below that. Some hosts even let you choose where in your directory structure to put them.
Rather late, but this question came up in the sidebar and the accepted answer is not really correct.
Subdomains, as far as the Internet is concerned, are completely separate from each other.
How a provider sets up the file structure is entirely up to them.
If you have VPS (virtual private server) with root access you can set it up any way you feel like, it's just a matter of putting the correct path in the webserver's config file.