Predestination is one of the deepest mysteries of the Christian Faith, but being a Dogma all are required to believe in it.  That said, the precise details of how one is to understand the Dogma are not defined, mostly because such a definition and understanding is beyond man's finite capacity to formulate and comprehend it in toto. Instead, the Church has given us "parameters" of sorts, which are supporting Dogmas that protect the faithful from embracing a wrong (and even dangerous) view of Predestination.
The following are some important "accessory" Dogmas that are to be kept in mind when either formulating a view on Predestination or to correct an erroneous view when dialoguing about this complex but important subject with various Protestant groups:
• One must affirm Free Will in man both starting with Adam and continuing to exist in man after Adam. 
• One must affirm that not only all men, but even Adam before the Fall required grace (and cooperation by his Free Will with it) to do good works and merit eternal life. 
• One must affirm that God is not the "author of sin," such that any sin is caused directly or indirectly by Him such that the individual could do no otherwise. Rather, all sin comes from (abuse of) the free choice the sinner - God merely permits sin, either for a greater good or to avoid a greater evil. 
• One must affirm it is possible to lose one's salvation, thus they must reject "Eternal Security" (sometimes called "once saved, always saved"). "God does not forsake those who have been once justified by His grace, unless He be first forsaken by them." 
• One must affirm that Christ died for all men, not only for those who attain final salvation, but only partakes in the merits of Christ through the exercise of faith and baptism. 
• One must affirm that, in the words of St Augustine, quoted verbatim by the Council of Trent: "God does not command impossibilities, but by commanding admonishes thee to do what thou canst and to pray for what thou canst not, and aids thee that thou mayest be able." This means that God gives everyone sufficient grace to choose to obey His commands, including repenting and turning to the Gospel. 
Each of the above points should be committed to memory, as they are all very important. Further, each of those points is fully defended (not just explained) by the Church to one degree or another.
The subject of Free Will has been a hotly contested subject throughout history, particularly at the time of the Protestant Revolt. The general contention of objectors centered around two things: (a) how can man have Free Will if God is Sovereign and predestines?, and (b) if Free Will ever existed, it only existed with Adam, and was forever lost by his disobedience.
Starting with the second issue, let's say Adam did indeed have Free Will to being with: given that we know God's Sovereign Plans have existed from the beginning, this demands we affirm both Free Will and God's Sovereignty truly co-existed, at least with Adam, thus proving conclusively that such a coexistence is not impossible. Further, since God sees all moments of time at once, there is not even a 'chronological' problem, as the Catechism of the Catholic Church points out in paragraph #600:
"To God, all moments of time are present in their immediacy. When therefore he establishes his eternal plan of "predestination", he includes in it each person's free response to his grace: "In this city, in fact, both Herod and Pontius Pilate, with the Gentiles and the peoples of Israel, gathered together against your holy servant Jesus, whom you anointed, to do whatever your hand and your plan had predestined to take place." [Acts 4:27-28] For the sake of accomplishing his plan of salvation, God permitted the acts that flowed from their blindness. [Mt 26:54; Jn 18:36; 19:11; Acts 3:17-18]"
Such reasoning should be accepted by any fair minded individual. Now the question that remains is whether Free Will remained after Adam sinned.
In a famous Encyclical by Pope Leo XIII devoted to addressing false understandings of Liberty, he begins by brilliantly establishing the reality of Free Will, which Liberty depends upon:
"Liberty, the highest of natural endowments, being the portion only of intellectual or rational natures, confers on man this dignity -- that he is "in the hand of his counsel" (Ecclesiasticus 15:14) and has power over his actions. ... The unanimous consent and judgment of men, which is the trusty voice of nature, recognizes this natural liberty in those only who are endowed with intelligence or reason; and it is by his use of this that man is rightly regarded as responsible for his actions. For, while other animate creatures follow their senses, seeking good and avoiding evil only by instinct, man has reason to guide him in each and every act of his life. Reason sees that whatever things that are held to be good upon earth may exist or may not, and discerning that none of them are of necessity for us, it leaves the will free to choose what it pleases. But man can judge of this contingency, as We say, only because he has a soul that is simple, spiritual, and intellectual..." 
Though there is a lot more that can be said, the important information to take away is this: what separates human nature (humanity) from the rest of creation, including other animals, is that he possesses a rational nature. This is characterized by human nature having a soul that is immaterial (i.e. not made of matter) and intellectual (i.e. able to reason). Animals can only go by instinct, that is simply a "gut feeling" at a given moment; they cannot study and deliberate and choose between various options, including acting against their reason and instinct. Reason alone (properly enlightened) tells us all this, as well as the fact Free Will is the only way man can be validly counted as responsible for his actions (cf. Gen. 4:4-7). This is a classic example of how the Church has utilized all it's tools to defend the Truth and easily expose and overthrow error. The Protestants who either reject or denigrate Free Will are logically forced to admit man's actions are either foreordained or of necessity, like gravity, and thus either shouldn't be responsible for breaking any laws (since it's out of his control), or worse yet, that God gives (impossible) commands with the goal of wanting man to break His laws for the purpose of punishing him.
To make the dilemma all the more outrageous, if a Protestant wants to say Free Will was lost when Adam sinned, they're forced to say human nature itself was lost, since that would require a new non-rational nature resulting (a humanity "version -1.0" of sorts), which is effectively that of an animal or worse. Liberty is called "the highest of natural endowments" by the Pope, meaning it is an integral part of our human nature and cannot be alienated from us, Fall or no Fall. To believe otherwise is the heresy of Manicheanism, and leaves Jesus unable to assume our human nature any longer (since He'd have to take on Adam's humanity and ignore our 'alternate' humanity. But we know Jesus took on our humanity (taking the title of 'Second Adam'), and His life was the epitome of Free Will cooperating with grace, all predestined to a glorious end.
Now this is not to say man can save himself by his own human abilities (e.g. his Free Will alone). He needs to cooperate with grace, which even Adam had to do, as noted earlier.  We know Adam required God's assistance (grace), not just because man cannot merit an infinite reward with finite human acts, but because human nature cannot experience God in His Glory without God enabling us to do so by His assistance (grace). A few quick and easy proofs that Adam's human nature (prior to his sin) was graced with divine gifts and thus 'elevated' from a natural to a super-natural (literally: "beyond" natural) state are as follows:
(1) We know Adam would not die so long as he continued to obey God's commands, yet, being a creature his material body would have had to been decaying day by day, for the body is not naturally immortal. Thus, he must have had a special grace of immortality preventing his body from decay.
(2) We know Adam and Even were originally "naked and not ashamed," meaning they originally didn't view each other as “sex objects,” but rather as a person with dignity and natural needs and desires. What differentiates human relations from that of animals is that animals act solely on the natural instinct to mate, where as human nature (being between animal and angel) has the added and superior “spiritual” dimension of communicating love by an act of the will. The reason why animals cannot lust is because they cannot love. Thus, lust occurs when the natural animal instincts to mate is acted upon, even if only mentally, without properly 'subordinating' it to the natural spiritual instincts of communicating love. This implies Adam originally had a special grace of 'proper subordination of passions' (traditionally called “integrity”), and only sought to dominate his wife afterward, just as animals dominate each other. The loss of this gracious gift results in concupiscence, meaning the animal instincts are not in harmony with the good the rational soul is ordered towards, causing improper appetites for sex, food, etc. St James tells us these concupiscence temptations are not lust unless acted upon by the will.
(3) We know that Adam being a creature couldn't know or believe in God without some sort of assistance, which is where the gracious gift of faith comes in. Hebrews (11:1,6) tells us that faith is believing in things we cannot see because they are beyond our limited, created capacity. Just as man needs a telescope to see far off stars he cannot otherwise see with his naked eye (i.e. natural powers), similarly did Adam need faith to raise his thoughts and inform his intellect of the divine things.
(4) We know that Adam was originally in intimate communion with God, which is by far the most spectacular experience of them all. There is no closer intimacy than God dwelling within your soul, which is precisely why St Paul says our bodies are “Temples of the Holy Spirit,” Who indwells in them (1 Cor. 6:19f), and pours out His divine love within them (Rom. 5:5). This is undoubtedly the greatest gift given to man.
Given these proofs, and given that we know human nature itself has not undergone a fundamental change, we can see the effects of the first transgression upon humanity: Adam came crashing down from the super-natural height he was originally enjoying in ease and comfort. Now he lost communion with God (at least temporarily), lost his gifts of immortality, integrity, et al, and was forced to live without these comforts and unable to pass these gifts on. Original Sin in essence is being born lacking the divine gifts that elevate human nature; thankfully, God was merciful enough to restore a few of them, especially the most important gift of the infusion of divine charity and the Holy Spirit. Even so, the Fall of Adam was truly was a disastrous fall from grace. 
With all that in place, it can be said the main points originally stated have been sufficiently proved. When it comes to the issue of Predestination, a few points specific to it should be kept in mind:
• Scripture only uses the term “Predestination” (in relation to salvation) in a 'positive' sense, meaning it is only spoken of in terms of Predestining to something good, never to something bad. Thus, to speak of a “double” Predestination as Calvinist Protestants do, with a counterpart speaking of a Predestination to evil or to hell, is plainly unscriptural.
• Scripture only uses the term “Predestination” a few times at all, the most well-known being Romans 8:29-30: "For whom he did foreknow, he also did predestinate to be conformed to the image of his Son, that he might be the firstborn among many brethren. Moreover whom he did predestine, them he also called: and whom he called, them he also justified: and whom he justified, them he also glorified." While the occurrence in Romans 8:29-30 is the most popular and closest sounding to “Predestined to Heaven,” it need not be taken to mean “Predestined to Heaven,” as certain Early Church Fathers such as St John Chrysostom state the term “glorified” applies to receiving the indwelling of the Holy Spirit, which corresponds to how the term “Predestined” is used in Ephesians 1:14 ("As he chose us in him before the foundation of the world, that we should be holy and unspotted in his sight in charity. Who hath predestined us unto the adoption of children through Jesus Christ unto himself: according to the purpose of his will").
• Scripture does teach the concept of Predestination, even in places where the term is lacking, but in no case does it imply Free Will is negated. Quite the contrary in fact. For example, Calvinists like to appeal to John 6:39 and John 10:28, but in Greek the verbs (e.g. 'draw', 'believe') are in the present-tense, meaning they're not speaking of a completed event of the past, but a 'presently-ongoing' action of Jesus and the believer. Thus by the very grammar this means Jesus will continue to draw and protect the believer so long as the believer continues to believe and continues to listen. In situations like Romans 8:28, the phrase “all things work together for good for those who love God” as proof Free Will is being taken into account. And some have taken the use of the term “foreknew” in 8:29 to mean something akin to foresee who would respond positively to God's grace - though in fairness there is also a tradition within the Church that also interprets “foreknew” as “foreloved,” and thus the person was predestined precisely because they were first loved. The case against Free Will is not established by the Scriptures.
• Texts like Romans 9, though always coming up in this discussion astonishingly doesn't use the term “Predestination” at all, giving some the impression that's not the focus. Instead, there are some who say Romans 9 is to be read as a single unit along with Chapters 10-11, which show the thesis is really about the Jews, who despite being graced with all these blessings none the less fell away and swapped places in God's sight with the Gentiles who were traditionally seen as 'second-class'. This is how I personally see it, particularly when one notices Paul quotes the OT in these chapters more times than any other place, and reading the OT passages in their original context reveals each time it's about God punishing the Jews for turning to sin (with key allusions to texts like Jeremiah 18).
• I personally opt for the term “Providence” instead of Predestination, because it helps remind me God is literally working through everything to bring about His Will, and we're living and interacting right within it. For those who are faithful and trust in God, He Will never abandon them, just as the Church teaches: "God does not forsake those who have been once justified by His grace, unless He be first forsaken by them." God doesn't desire us to perish, and thus it's ultimately our fault with God having been merciful enough to warrant any deserved condemnation of us in the end. And the fact He gives us the chance to repent and get to Confession is also proof of His mercy, though not that we should presume His mercy, which is a grave sin in itself.
One final point I'd like to address is the antelapsarian (ante=before, lapsarian=lapse, to fall) and postlapsarian (post=after) theories among Calvinists in regards to the 'ordering' of God's plan for predestination being before the Fall or after the Fall. This is important because this is what their pet doctrine of “double predestination” comes from. In double predestination, God determines not only to save a person 'unconditionally', which isn't that bad, but also to damn the rest 'unconditionally', meaning for no other reason than His good pleasure. Of course, this is an abomination, but the Calvinist mind sees it as necessary. This is typically understood to take place as follows: God first decides who to damn, He then positively foreordains the sin of Adam precisely to put those reprobate souls on the path to hell, with no way out and refusing any graces to save them. This requires the antelapsarian view (also called supralapsarian, supra=beyond). This is what many Calvinist scholars state Calvin held to, and indeed is the most logical. 
Other Calvinists don't like this (for the same reason as us non-Calvinists). But this leaves the postlapsarian view, which has it's own problem, though it is closer to an acceptable Catholic view. In a postlapsarian scenario, God first permits (not foreordaines) the Fall, and then uses this as an opportunity to show His mercy on some and simply abandon the rest in sin. But at that point God isn't forming a plan of predestination from eternity, since Adam cannot be said to be predestined in this scheme, and this also ignores the fact Christ died for all and God doesn't command the impossible.
A third group of Calvinists say either view is unacceptable due to the fact Scripture doesn't give such details, but the problem here is that it ignores the fact that double predestination was so critical for Calvinism and must be maintained as an integral part of Calvinist doctrine. This dilemma ultimately vindicates the Catholic view, in which “Predestination” is not used in the sense of 'rescuing' people already in sin, but rather Predestining as an added grace from the start of creation, since Adam as a creature never deserved nor was owed heaven to begin with. The very initial gracing of Adam's nature was a mini-predestination, and he fell by his own sin.
Next time, we will look at Catholic thinking on this problem throughout the ages, focusing on the thinking of Augustine, Aquinas, and the Jesuits.
 The Council of Trent, Session 6 (Decree on Justification) says this in Canon 15: "If anyone says that a man who is born again and justified is bound ex fide to believe that he is certainly in the number of the predestined, let him be anathema." This Canon references back to Chapter 12 (of Session 6) where it states: "No one, moreover, so long as he lives this mortal life, ought in regard to the sacred mystery of divine predestination, so far presume as to state with absolute certainty that he is among the number of the predestined, as if it were true that the one justified either cannot sin any more, or, if he does sin, that he ought to promise himself an assured repentance."
 Ibid. Canon 5: "If anyone says that after the sin of Adam man's free will was lost and destroyed, or that it is a thing only in name, indeed a name without a reality, a fiction introduced into the Church by Satan, let him be anathema."
 Ibid. Canon 2: "If anyone says that divine grace through Christ Jesus is given for this only, that man may be able more easily to live justly and to merit eternal life, as if by free will without grace he is able to do both, though with hardship and difficulty, let him be anathema." (cf. Council of Orange, Canons 7 and 23)
 Ibid. Canon 6: "If anyone says that it is not in man's power to make his ways evil, but that the works that are evil as well as those that are good God produces, not permissively only but also propria et per se [i.e. by God's active causing of it to happen], so that the treason of Judas is no less His own proper work than the vocation of St. Paul, let him be anathema." And Canon 17: "If anyone says that the grace of justification is shared by those only who are predestined to life, but that all others who are called are called indeed but receive not grace, as if they are by divine power predestined to evil, let him be anathema." See Council of Orange, Conclusion: "According to the catholic faith we also believe that after grace has been received through baptism, all baptized persons have the ability and responsibility, if they desire to labor faithfully, to perform with the aid and cooperation of Christ what is of essential importance in regard to the salvation of their soul. We not only do not believe that any are foreordained to evil by the power of God, but even state with utter abhorrence that if there are those who want to
believe so evil a thing, they are anathema."
 Ibid. Canon 23: "If anyone says that a man once justified can sin no more, nor lose grace, and that therefore he that falls and sins was never truly justified ... let him be anathema." (cf. Chapter XI)
 Ibid. Chapters 2-3: "... [Christ] has God proposed as a propitiator through faith in his blood for our sins, and not for our sins only, but also for those of the whole world. But though He died for all, yet all do not receive the benefit of His death, but those only to whom the merit of His passion is communicated..."
 Ibid. Chapter XI
 Leo XIII, Encyclical Libertas Praestantissimum. Sections 1, 3.
 Council of Orange, Canon 19: "That a man can be saved only when God shows mercy. Human nature, even though it remained in that sound state in which it was created, could be no means save itself, without the assistance of the Creator; hence since man cannot safe- guard his salvation without the grace of God, which is a gift, how will he be able to restore what he has lost without the grace of God?" Also, I strongly encourage you to listen to the wonderful Lectures and read the accompanying Article hosed at the website Called To Communion on the subject of how to properly understand man's nature: http://www.calledtocommunion.com/2011/10/protestant-objections-to-the-catholic-doctrines-oforiginal-justice-and-original-sin/
 Protestantism from the start has been repulsed by the Catholic distinction between nature and grace, especially starting with Adam. But the rational and Scriptural proof is plain and the arguments are sound. The Protestant “alternative” is that man didn't have those gracious gifts, and instead could do all those things according to natural human abilities. Not only is this blasphemous, it's the very error of Pelagius. Most people know Pelagius denied anything happened to man after the fall and thus denied God's grace for salvation, but what they don't know is that Pelagius denied man fell precisely because he denied man was originally graced as Catholics say Adam was, and thus there was nothing to “fall from”. Taking Pelagius' same error to a greater extreme, Protestants say human nature itself became corrupt, being transformed into a “sin nature”. But such is sheer blasphemy, for (as noted above) this means Christ couldn't have inherited our nature. And to compound this, it entails that what Adam had to do by purely natural powers (including keep God's commandments perfectly), Christ had to do all this (including keep the commandments perfectly) by purely natural human powers - which is
heretical because Christ a Divine Person with a Divine Nature and cannot divorce this from natural human actions.
 See this wonderful article by Catholic Apologist Dave Armstrong for the details: http://socrates58.blogspot.com/2006/06/calvin-supralapsarianism-and-gods.html