I think the main reason that people say that "everything Hitler did was legal" is because they are warning that we might somehow legislate ourselves into a similar situation to Nazi Germany, and are saying that we have to remember that there is ultimately a higher standard of justice than just what the law happens to be. These are worthy goals but unfortunately they are founded on a misunderstanding of the Nazi rise to power, and thus they obscure the true lessons to be drawn from it.
The basic point is this: Hitler was not a product of tyranny, but of anarchy. The Nazi regime was not a product of a process of the creeping extension of state power, but a product of the complete breakdown of civil order and the power of the state. The Nazis took power essentially as an armed insurrection that was able to seize the state because the state was so weak. Once he was in power, Hitler was of course a tyrant and the instruments of rule all too powerful; but it was the very weakness of these instruments that allowed him to get there in the first place. The lesson of the Nazi rise to power is that we must not let the state get so weak that anarchy prevails; the over-reaction into tyranny is all too predictable
It is hence very hard to extend this analogy to any modern western country today. For America to repeat the Nazi experience, the military would have to virtually cease to exist and civil war would have to reign between armed militias of millions of citizens; the economy would have to deteriorate to the point where money was worthless and no-one any longer had a stake in the political system; and this political system would have to become virtually powerless.
This is how things stood in Weimar Germany, which was the political system in place before the Nazis took power. What is legal and illegal in such a situation is a technicality because the very power of the law has become questionable and facts are dictated by the armed groups, not by the courts. The fact that "Hitler was elected" really means nothing except that people will embrace strength when they are surrounded by chaos; people were willing to vote for him not because he was a legitimate politician who can be said to have been campaigned fairly, but because he was the head of a vast, violent movement that looked the strongest of the various options. When his brownshirts were murdering political opponents, nothing like a fair election can be said to have taken place.
The Nazis poured scorn on the legal institutions of the Weimar Republic because they knew that they had what mattered: force. There were four million Germans in the Nazi brownshirt organization by 1934, and Hitler rode them into power. Weimar democracy and its laws were so unenforced and discredited that the state could not stop them - they outnumbered the army and the police. Weimar's laws were so weak that they had allowed armed groups such as these and the Communists - whom the Nazis loathed but tolerated for as long as they helped to undermine the democratic system - to dominate the country. With these armed groups roaming at will, ordinary citizens ceased to see the legal system as their protector, learning that they had to rely on those with the guns.
When the Nazis were in power, they passed laws that retroactively legalized the crimes they had commited on the path to power, and that covered everything they did while they were there. They were unusually concerned with inventing a whole new concept of justice and jurisprudence, and over-eager intellectuals were happy to oblige. Yet the essential fact of Nazi "law" was that Hitler, as the embodiment of the German people, could do no wrong; everything that the Fuhrer did was legal by definition. The laws passed in the Reichstag as a cover for their various activities were just a sop to bourgeois sentiment, and were scorned by hardcore Nazis. Had Germany won the war and the real Nazi revolution begun, rest assured there would have been no Reichstag anymore.
Laws can be wrong and some of our laws may be wrong. But the true lesson of the Nazi rise to power is that if the law itself becomes so discredited that no-one has the will to uphold it, and the state becomes so far removed from the people that they have to look to armed groups for protection and the advancement of their interests, then fanaticism is likely to emerge out of the maelstrom. The lesson is that we must never allow the rule of law to become so weak and so despised.
Barring major war or economic collapse - both of which Germany suffered before the Nazis - we are not likely to be faced with a weak state. Yet the law itself may be discredited if it comes to be seen as an enemy of the citizen and a persecutor of the weak; it must hence tread ever more carefully on the fine line between our liberty and our security that it has tread since the dawn of time. Our security is important because otherwise people will look elsewhere for protection; in extremis, armed groups will roam the streets. And our liberty is important because the zone of freedom created by the law is what justifies the law's existence in the first place. The Nazi example warns us of the dangers of losing either.