@mysteryman,
Walter has laid out how this happened, but i'll append a few notes that might make it clear to you. In most constitutional democracies, a Prime Minister is elected to a seat in the legislature, whatever it's form, but is not elected nationally. So, Stephen Harper is the Prime Minister of Canada, even though he was not elected nationally, but only within his riding. This was not quite the same in Germany (and in several other countries), where the head of the party becomes the Prime Minister (or, in this case, the Chancellor) if his party takes the most seats--so to revert to the example of Canada, Stephen Harper is the Prime Minister because his party won the most seats.
Finally, in many (most?) nations, there are several political parties which qualify for national elections. In Canada, there are four, although one of them--the Bloc Quebecois--is not a national party. So the ruling party frequently just has the most seats, not necessarily a majority of seats. In Harper's first government in Canada, he did not have a majority, just the most seats. That means he had to form a coalition, get one or more other parties to support his legislative agenda.
Finally, when there are several parties, someone can "win" and form a government without having a won a majority of votes, just a significant fraction. So, to refer to the example of Stephen Harper again, in the last election, he won a "majority." That means the Tories won over 50% of the seats (just barely, 50% plus one)--but with several parties fielding candidates in each riding (voting district), the Tories got just less than 40% of the vote. If three or four candidates run in a riding, the one with the most votes wins, which is not necessarily 50% of the vote. This has an important effect on politics. Harper has a "majority" government, but he knows that the Tories aren't that popular. He largely won because the New Democrats gave the Liberals a drubbing. That means the New Democrats won an unprecedented number of seats--but it also means that the Tories won some ridings they had never won before because the NDP and the Liberals split the majority of the vote, leaving the Tories with the most votes,
for any single party. So Harper has to be careful not to create a situation in which enough voters get disgusted with the Tories and desert them for the NDP or the Liberals.
So, back to Germany, 1933. Hitler only got 35% of the vote when he ran for President--and the NSDAP (the Nazis) got 35% in the Riechstag . That wasn't a majority, but it was more than any other party. After the Richstag fire, in the next election (Germany was having elections like NASCAR has races), the NSDAP got 45% of the vote (fractionally less than 45%, i believe), which meant they still had the most seats, but not a majority. Therefore, in order to govern, Hitler had to form a coalition. He formed a coalition with a right-wing party, the DNVP (which are the initials of the German words which mean German National Peoples Party).
Finally, he passed the enabling act, which gave him the right to legislate without reference to the Riechstag. This was, i believe, set up by Bismarck in the 1860s (Walter will know) to give the Chancellor necessary powers in time of emergency. To pass that enabling act, he needed a two thirds vote. He got the Centre Party (the national Catholic party) to vote with the NSDAP and the DNVP by promising reforms which would benefit Catholics, and end institutional discrimination against Catholics. Like a parcel of fools, they agreed--and the head of the DNVP had once been a prominent member of the Centre Party, which didn't hurt.
Hitler's rise to power was completely legitimate in constitutional terms.