What does it mean to say that the pope is infallible? Does this mean that he never makes any mistakes, never sins, or that he is perfect?

The doctrine of Papal Infallibility [1] was formally defined at the first Vatican council in 1870, but its roots run much deeper:

When Jesus went into the region of Caesarea Philippi he asked his disciples, "Who do people say that the Son of Man is?" They replied, "Some say John the Baptist, others Elijah, still others Jeremiah or one of the prophets." He said to them, "But who do you say that I am?" Simon Peter said in reply, "You are the Messiah, the Son of the living God." Jesus said to him in reply, "Blessed are you, Simon son of Jonah. For flesh and blood has not revealed this to you, but my heavenly Father. And so I say to you, you are Peter, and upon this rock I will build my church, and the gates of the netherworld shall not prevail against it. I will give you the keys to the kingdom of heaven. Whatever you bind on earth shall be bound in heaven; and whatever you loose on earth shall be loosed in heaven." (Matthew 16:14-19).

We can trace in an unbroken line all of the popes, from Benedict XVI back to Peter the apostle; and just as we believe that the bishops are the successors of the apostles, we believe that the Pope, as earthly head of the Church, is the successor to the "head" apostle, Saint Peter. As such, he is the visible head of the Church on earth and the vicar of Christ, who Is the Head of the Church (Ephesians 5:23).

Now consider that in the Catholic understanding, Peter is the rock upon which Christ builds His Church. Let me say that again, because it is important, and a difference between Catholic and (most) Protestant interpretations of this passage: Peter is the rock on which Christ chooses to build His Church—not Peter's faith, or his obedience, or any of his other virtues, but Peter himself, and by extension Peter's successors.

The gates of the netherworld cannot stand against the Church. This means that even the very prince of darkness and lord of lies himself—the devil Satan—cannot withstand the Church. This means that the lies which the devil spreads cannot defeat the Church, and thus that the Church should be able to teach not only authoritatively, but also truthfully, on at least those matters of importance to our salvation: matters of faith and morals. There are, in turn, three ways in which the Church teaches infallibly: through the "Ordinary Magisterium", through ecumenical councils [2] in union with the pope, and through the pope teaching ex cathedra.

There are four conditions concerning a pope's exercise of infallibility. Here is how the doctrine was promulgated by the First Vatican Council:
Faithfully adhering to the tradition received from the beginning of the Christian faith … we teach and define that it is a dogma divinely revealed that the Roman Pontiff, when he speaks ex cathedra, that is when in discharge of the office of pastor and teacher of all Christians, by virtue of his supreme Apostolic authority, he defines a doctrine regarding faith and morals to be held by the universal Church, by the divine assistance promised him in Blessed Peter, is possessed of that infallibility with which the Divine Redeemer willed that His Church should be endowed for defining doctrine regarding faith and morals; and that, therefore, such definitions of the Roman Pontiffs are irreformable of themselves, and not from the consent of the Church.
Here are the criteria again. First, he must be intending to teach, and second to teach by his authority as pope; third, it must be on a matter of either faith or morals, and fourth it must be a teaching meant for the whole Church. When all four of these conditions are met—and only then—the Pope enjoys a guarantee that the Holy Spirit will preserve his teaching free from error.

This list of criteria does, incidentally, eliminate the very vast majority of papal works—even papal teachings!—from that guarantee of infallibility. Thus, for example, our current pope's book Jesus of Nazareth—a book which he has written since his election as pope—is not an infallible teaching, since he has stated that it is not intended to be such; nor are his Wednesday audiences, since they are not addressed to the whole Church; etc. Two works which do include exercises of infallibility by popes are Ineffabilis Deus (in which the dogma of the Immaculate Conception is defined) and Munificentissimus Deus (in which the dogma of the Assumption of Mary is defined) [3].

There are many works of apologetics which consider infallibility in general and papal infallibility in particular, and I won't have time to look at these in-depth here. However, I will offer one argument which gives support to this doctrine (because it also helps to explain the dogma logically). This argument comes from EWTN's Dr Jeffrey Mirus, who writes that
Since the successors of Peter have the same Petrine authority, which comes ultimately from Christ, to bind and loose, they have the authority to bind the faithful in matters pertaining to salvation -- that is, in faith or morals. Now, if a Pope could bind the faithful to error, it would be a clear triumph of the powers of Hell, because the entire Church would be bound to follow the error under Christ's own authority. Obviously, this cannot happen.

Therefore, the logic of the situation demands that the Petrine power of confirming the brethren must be an infallible power. When the Pope intends by virtue of his supreme authority to teach on a matter of faith and morals to the entire Church, he MUST be protected by the Holy Spirit from error -- else the powers of hell would prevail.

Here I should return to the question at hand by way of stating a few things that infallibility is not. Infallibility does not mean that the pope is perfect. Only God is perfect, and though the pope is the Vicar of Christ, he is still well short of being God. Infallibility does not mean that the pope is sinless, or morally perfect, or preserved from all future sins (this is "impeccability," not "infallibility"). To pick only one example, every pope has a personal confessor—meaning a priest to whom the pope confesses his sins to ask for God's (and the Church's) absolution; this would be unnecessary if the pope were sinless. Of course, we have been relatively blessed by our last few popes in the holiness department [4], so other examples of papal sin are a bit more apparent in past centuries!

Finally, infallibility does not mean the pope will always be right in everything he says (that is, "inerrant"); it does not even mean that he will always rightly teach about matters of faith of morals! To see what I mean by this, consider Catholic Answers' discussion of Pope Honorius and the Monothelites in their essay on infallibility:
According to Fundamentalist commentators, their best case lies with Pope Honorius. They say he specifically taught Monothelitism, a heresy that held that Christ had only one will (a divine one), not two wills (a divine one and a human one) as all orthodox Christians hold.

But that’s not at all what Honorius did. Even a quick review of the records shows he simply decided not to make a decision at all. As Ronald Knox explained, "To the best of his human wisdom, he thought the controversy ought to be left unsettled, for the greater peace of the Church. In fact, he was an inopportunist. We, wise after the event, say that he was wrong. But nobody, I think, has ever claimed that the pope is infallible in not defining a doctrine."
There is, in other words, a bit of a difference between being "always right" and just "never wrong." Preservation from error in defining doctrines of faith or morals falls squarely into the latter category. And of course, the charism of infallibility does not apply at all to when the pope is teaching about subjects which are not a matter of either faith or morals, since this would not meet all four of the criteria to which the doctrine applies [5].

The doctrine of infallibility if not, therefore, a safeguard for the pope's own sanctity, nor against his looking foolish by a slip of the tongue (for example). Rather, it is a protection of the whole Church by the Holy Spirit against being led into error by teaching a falsehood as a matter of truth in faith or morality. It means that the Church as a whole and the pope as her visible head in particular are "incapable of error or deception" when binding or loosing as a matter of universal faith or morality. This is a charism of the pope, but it is a gift from Christ to His whole Church.

--Footnotes--
[1] Note that Papal infallibility was defined as a dogma in 1870, though exercised in practice before then (e.g. in the doctrine of the Immaculate Conception, which was a few years before this council, but also in other older instances). Infallibility of the the Church's Magisterial (teaching) authority has always been understood and accepted as a doctrine. The time at which a dogma is defined is not the same as the time at which it becomes true, as Dr Jeffrey Mirus explains:
While the the First Vatican Council defined papal infallibility in 1870, you must understand that the date on which a doctrine is officially defined is not the date on which it becomes true. Rather, it was always true. It's just that different aspects of the Faith are challenged at different periods of history, and when a challenge occurs or a serious concern or question arises, then the Church will settle the difficulty by formally stating what the truth of the matter is -- to end the confusion. So papal infallibility has always been true, and, moreover, was accepted and practiced from the earliest times.

[2] From the Catholic Encyclopedia article on infallibility, here is the definition of an "ecumenical council":
An ecumenical or general, as distinguished from a particular or provincial council, is an assembly of bishops which juridically represents the universal Church as hierarchically constituted by Christ; and, since the primacy of Peter and of his successor, the pope, is an essential feature in the hierarchical constitution of the Church, it follows that there can be no such thing as an ecumenical council independent of, or in opposition to, the pope.

[3] Some would argue—including, significantly, the future pope Benedict XVI—that the teaching found in Blessed Pope John Paull II's Ordinatio Sacerdotalis is also infallible (that is, that the teaching which it contains about the impossibility of ordaining Woman as priests is an infallible teaching). That the teaching is binding is beyond doubt; but whether it was first defined infallibly by Blessed John Paul the Great or by the Ordinary Magisterium is topic for another day.

[4] The last 5 popes are all under consideration for canonization. Two have been beatified already, one declared "venerable" (meaning that the investigation process has found him to be possessed of "heroic virtue," and the other two are each named "Servant of God." Given that our current pope, Benedict XVI, is a possible future candidate for canonization as well, this means that we have had apparently holy and possibly even saintly men on the throne of St peter since 1939. In other centuries, the Church has not been so blessed.

[5] It is probably also worth noting that even when the pope is teaching infallibly about faith or morals, the Holy Spirit's preservation from error of the doctrines in question only applies to the core doctrine being taught, and not necessarily to the whole document by which it is promulgated.