It is often supposed that there were two sides to Machiavelli, as a superficial reading of his two most famous works (The Prince and the Discourses on Livy) seems to show a dichotomy between the two. Really, no such split exists, as I shall show in this brief summary of his ideas.
First, The Prince. Being much shorter and less enigmatic than his other work, it is often the one on which an understanding of him is based. Yet Machiavelli tells us right at the start that in this work he is concerned only with the government of principalities. "I shall not discuss republics, because I have previously treated them at length." Furthermore, he won't be talking about just your average principality either -
I say at once there are fewer difficulties in holding hereditary states, and those long accustomed to the family of their prince, than new ones; for it is sufficient only not to transgress the customs of his ancestors, and to deal prudently with circumstances as they arise, for a prince of average powers to maintain himself in his state, unless he be deprived of it by some extraordinary and excessive force; and if he should be so deprived of it, whenever anything sinister happens to the usurper, he will regain it.
It is "in new principalities that there are real difficulties". So The Prince is only about one sort of government (a principality, ruled by one man) and only about new principalities - ones newly acquired by their ruler, probably through conquest. Such a situation had just occured in his native Florence, where the Medici family had newly returned to power on the back of Spanish arms. Hence The Prince cannot be taken as a complete rendering of Machiavelli's political theory, as it deals with only a certain type of state. It is a handbook for princes, and the subject is how to stay in control of new conquests.
What was particularly shocking to contemporaries about Machiavelli's book were the measures he advised for the new prince to maintain himself in power. We're used to viewing politicians and states cynically, and so were most people in Europe at the time Machiavelli was writing. However, what didn't exist in Europe at the time was a genre of political literature advising that princes act in cynical and violent ways to manipulate the populace. They did it anyway, but political discourse wouldn't admit it. The fact we have such a surplus of literature condemning such things today owes to the reaction against Machiavelli, who for the first time suggested princes should break faith, be violent, and bamboozle their subjects so as to maintain power.
Machiavelli's prince was a strong man (vir), a man of virtu (efficiency, will, courage) who had overcome his enemies and conquered a new principality. But he would not long remain in power if he let the initiative pass to his enemies inside or outside the city, and he had to continue acting boldly to overcome nature. Machiavelli was the first author who saw citizens as passive objects to be manipulated, and the state as an actor doing the manipulating. For the prince to remain in power, he had to do everything necessary (but no more) to stage a political theatre that would please his subjects and make him feared by other princes. What was necessary was necessary, whether it contravened Christian or classical moral precepts.
Machiavelli had created a new moral universe which ran parallel to the individual one, a morality for states. This would later be called "the reason of states", or raison d'etat. If this were Machiavelli's only legacy, his negative reputation might be more justified - after all, he essentially encouraged princes to look after no other interest but their own, and to do anything towards that end. The only parameter he set for this was that anyone who committed more violent and unholy deeds than was strictly necessary was to be considered lacking in fame and glory, and a beast in the negative sense.
It is in The Discourses that Machiavelli transcends this plane and establishes himself as not only a great practical political thinker, but also a defender of liberty. The remit of the The Discourses is larger, as within it Machiavelli sets about to discuss what it is that leads cities to greatness; specifically, the city of Rome. His concern is much broader than with a newly-acquired principality, and hence is answers are more complex and proved more amenable to the critical eye of his contemporaries and posterity.
Machiavelli was an avowed republican, by which I mean he loved the state-form we call "a republic", not that he would have voted for George W. Bush.1 He believed that a republic was much more capable of achieving greatness than a principality, because it was capable of harnessing the entire energy of its population against nature and the enemies of the state. This meant it was more able to suceed in war because its citizens would be fighting for their liberty.
Furthermore, republics would be better able to adapt to the times and hence overcome challenges that principalities could not. When situations changed and nature threw new challenges at the state, it could call forth different men from within it to face the new challenges. A principality was necessarily limited by the character of its prince, as individual men found it hard to be many different things - they might be bold when danger abounded, but would they be cautious when the opposite conditions prevailed? A republic would have more chance to adapt, and in Machiavelli's dog-eat-dog world to adapt meant to survive.
Machiavelli then, was no fan of narrow and tyrannical regimes. He tells us several times that the most edifying thing a prince can do is to set up a long-lasting republic, and he sings the praises of Romulus (founder of Rome), Lycurgus (founder of Sparta) and Moses (founder of the Hebrew theocracy). It takes the will of such demi-gods to shape nature and men into the right form for a state to have longevity, and to carry out this task is the true meaning of glory. So although Machiavelli's conceptual split between the state and its citizens allowed for abuses, it also allowed for future-oriented development on rational lines.
1. Whether he would or not would be a fascinating question. A connection is sometimes made by the left - Leo Strauss wrote a book on Machiavelli (Thoughts on Machiavelli), and Leo Strauss influenced neoconservatism. This sounds sinister until it is realized that Strauss' book on Machiavelli is a hatchet-job of arguments against the Florentine.
See also raison d'etat and The transformation of European political theory: the legacy of Machiavelli on the impact of Machiavelli's thought.