Whooooo, this is a doozie of a question! There are several approaches to this answer, some given in topo morto's comments, but I'll focus on two others:
Most modern instruments today use what is called 12-tone equal temperament. (Even wind instruments, tympani, etc. tune based on this system.) This means that that each tone is precisely 100 cents apart from the next one. C is 100 cents away from C♯, which is 100 cents away from D, etc. This wasn't always the case; throughout history there were various tuning systems. We call these "temperaments" because the pitches are "tempered" to fit into a particular system. In the Pythagorean system, perfect fifths were emphasized, which meant that major thirds were out of whack. In "concentric" systems, the system emphasized the most-used keys, meaning that keys like F♯ were basically unusable.
Thus, when past composers were using particular tuning systems, different keys could actually sound different. The "quality" of C major was different than the quality of E♭ major, and so the choice of key could have been a deliberate choice. Or if a composer knew he wanted the second section of the piece to modulate down a major third, he'd have a limited number of original tonics where both keys would be successful in a given tuning system.
But as I said, today we have 12-tone equal temperament. However, some instruments just work better in some keys. Orchestra brass will sound fuller and richer in a key like D♭ major than they will in B major, and (good) composers will use this to their advantage.
Some Remarks on Cognition
You're right that we'd all recognize the national anthem no matter what key it's in. We call it "absolute pitch" (some erroneously call it "perfect pitch") when someone can instantly recognize a pitch, a tonal level, etc. But here's something interesting! A study took several famous songs---for example, the Jeopardy! theme---and played it at two different pitch levels for a group of listeners (musicians and non-musicians alike). The majority of listeners could discern which recording was at the "actual" pitch level. (I'll try to find the source for this.) Long story short, there is good reason to believe that absolute pitch is really just long-term pitch memory, and not some innate ability to just grab pitches and keys out of thin air.
In other words, there could be cognitive reasons for using particular keys, but I would say we're still a little too early in our understanding to say for sure.