As Mje says above, removing one's hat has long been a sign of respect. As for the phrase "Hats off to...!" - which is what I presume you are asking about - that has been around only since the 1920s, as a sort of order to show that respect. You see it in such sentences as: 'Hats off to the English rugby team!'...'Hats off to the Black Watch!'...and so on. Strangely enough, the very earliest recorded version, which appeared in 'The Daily Mail' in 1923, said: "Hats off to France!"