Before Christianity in Europe, what was the big religion?

"Before Christianity" is, of course, a very long time, but if we restrict ourselves to the first milennium BC or so, it is not that likely that we would have recognized the cults, rituals and myth as "religion", which generally denotes some kind of dogma, central teaching, scripture, etc. The most widespread cults would probably have been Indo-European, but generalizations about Indo-European proto-religion, as much as I make use of them, are a bit of artifical constructs that do not necessarily reflect the practices of the everyman. There were recurring motifs, popular tales, etc, but no unified religion. A pretty common question on this subreddit is whether the Greeks "really believed" in their religion and there are a few answers, I like this one from /u/Daeres. I believe /u/itsallfolklore has written some great posts on the diversity of what we might call "folk religion" and how it differs from our conception of "religion", but for the life of me I can't find any of them.

Did people worship the gods like Zeus and Poseidon?

Yes. "Zeus" is a very old theonym that goes back to the Indo-European "Dyueus Phter", or "Sky-Father", a patriarch who was probably most strongly associated with ritual sacrifice. That same name is the root for Jupiter, "Deus" (but not Theos), "Divine", et cetera. Zeus in particular may have been influenced by Near Eastern storm gods like the Ugaritic Ba'al and Yahweh, because the patriarch in Indo-European mythos is usually not the storm god. Instead storms tend to be associated with club-wielding strongmen and warriors like the Vedic Indra, Norse Thor, and Slavic Perkunas, who all had very popular cults, symbolizing masculinity and the uncontrollable young warrior's martial virtues. The closest functional equivalent to these deities in Greek religion would be Heracles, who was of course very widely worshipped as well.¨

I guess my real question is how did their concept of karma work? Did people go to hell for bad deeds and heaven for good ones?

First, Karma as a cosmological concept is peculiar to Indic religions like Hinduism, Buddhism and Jainism. It is not a simple matter of "good deeds rewarded, bad deeds punished", but an understanding that as a consequence of the "fact" that death is an illusion, your deeds (literal meaning of Karma) have consequences that stretch beyond death.

Second, no, generally not, at least not in a systematized way (it is clear from e.g. Greek myths that various conceptions existed of some kind of continued existence after death at various times). To the extent ideas of afterlife existed at all, they seem to have pictured the hereafter as a shadowy, uneventful persistence.

The idea of heaven and hell probably emerged first with Zoroastrianism, which, while an Indo-European belief system, most likely resembled a religion much more than other such belief systems, due to the unifying teachings of Zarathustra (who ought to have lived in Uzbekistan or Turkmenistan around 1300 BC). While the Gathas, the seventeen great hymns of Zarathustra, do not explicitly mention heaven and hell, they discuss the problem of evil extensively, quoting here Yasna 46 in entirety:

1. For his holy Spirit and for Best Thought, deed, and word, in accordance with Right Mazda Ahura with Dominion and Piety shall give us Welfare and Immortality.

2. The best (work) of this most holy Spirit he fulfills with the tongue through words of Good Thought, with work of his hands through the action of Piety, by virtue of this knowledge: he, even Mazda, is the Father of Right.

3. Thou art the holy Father of this Spirit, which has created for us the luck-bringing cattle, and for its pasture to give it peace (has created) Piety, when he had taken counsel, O Mazda, with Good Thought.

4. From this Spirit have Liars fallen away, O Mazda, but not the Righteous. Whether one is lord of little or of much, he is to show love to the righteous, but be ill unto the Liar.

5. And all the best things which by this Holy Spirit thou hast promised to the righteous, O Mazda Ahura, shall the Liar partake of them without thy will, who by his actions is on the side of Ill Thought?

6. Through this holy Spirit, Mazda Ahura, and through the Fire thou wilt give the division of good to the two parties, with support of Piety and Right. This verily will convert many who are ready to hear.

The Gathas are incredibly cryptic, but here Zarathustra seems to pose the rhetorical question of whether "liars" (sinners, those who commit violence, etc), too, shall enjoy the Haurvatat and Ameretat (Wholeness and Immortality) promised by Mazda. This suspicion is confirmed in the first few lines of Yasna 47:

1. When at the Recompensings the Right shall smite the Liar, so that what was long since made known shall be assigned to eternity to Daevas and men, then will it exalt with thy blessings, Ahura, him who prays to thee.

2. Tell me, for thou art he that knows, O Ahura: - shall the Righteous smite the Liar before the retributions come which thou hast conceived? That were indeed a message to bless the world.

where Zarathustra seems to question whether it is truly enough that the evildoers will face divine retribution at some point in the future. At the end of Y 47 states who the judges will be:

12. These shall be those who bring benefit to the provinces, who exert themselves, O Good Thought in their action, O Asha, to fulfill their duty, face to face with thy command, O Mazda. For these are the appointed smiters of Violence.

The Avestan term for the bolded is Saoshyant - here we seem to see the first seeds to what would eventually develop into a messianic teaching that almost certainly influenced the messianic Jewish cults around the time of Jesus. (In Zoroastrianism, Zoroaster's seed has been preserved in Lake Hamun in Afghanistan, where it will impregnate three bathing virgins who will give birth to the three Saoshyants).

I'm not going to bore you to death with Zoroastrian theology you didn't ask for, but the concept of general retribution/reward in the hereafter the way we think of it from a Christian or similar point of view, only seems to have been introduced into the Near East with Persian dominion, and as far as I know there is no reason to believe it was a widespread idea in Europe prior to the advent of Christianity.