Having a template per category? Bad for server overhead?

I say “bad practice” because perhaps I am just adding a ton of overhead that WordPress has to loop through templates – or is it not a huge problem? Would the overhead be nominal?

No, there won’t be an extra performance cost because that’s not how the template loading works. WP always runs through the template hierarchy from most specific to most generic, testing if the file exists as it goes along. It doesn’t “loop” through them.

As for creating a template for every US state, I would advise against it, mainly because it means your folder will have a lot of files making it difficult to navigate in the editor, and when you want to make a change you have to update every single state.

You’d be better off making a single generic state template, or better yet, add a state taxonomy and create taxonomy-state.php instead of repurposing categories.