The Phrase Finder has the following excellent summary of this phrase's origin, which goes so far as to include a couple variations:
Origin: in more ceremonious days, if someone came to visit you, you would see him to the door at visit's end. Then either you or your butler would hand him his hat, since everyone in those days wore hats, but not inside. Figurative meaning: to be shown the door, to be sent packing. Can be used to mean to be fired.
You can use it in a variety of ways, such as: "He expected another term, but the voters handed him his hat." Or, "I was confident that my actions were for the good of the company, but I was handed my hat anyway." Or: "I offered him first crack at my new invention, the one that would save him thousands annually. I didn't expect to be handed my hat and shown the door."
Of course, the literal meaning is still valid. If you are looking around for your hat, someone is likely to hand it to you in simple politeness.
"Was handed his hat" gets 123 results on Google; using "her" gets 33, "their" gets 14, "being handed his hat" has 97, etc. I'd say it receives a respectable amount of attention, by no means ostentatious. To compare, "was shown the door" gets 560 results.