What does 'Rebuild Permissions' actually do? I've been working with a lot of custom content types lately, and I keep getting a message to rebuild my permissions.

It seems like it happens everytime I create a new content type. Is this normal behavior? And what exactly is happening when I do this?
Drupal core uses database tables to control some aspects of content viewing/editing permissions. These tables are used by contrib modules like Domain Access or Taxonomy Access Control to store information about which roles/users can see which nodes. Because it is not easily determinable which configuration changes will result in actual permission changes Drupal marks these tables as needing updating for a broad set of configuration changes.