Are you saying that no one had sex before marriage in Biblical times? Or are you saying that sex before marriage was already frowned throughout the whole Eastern Mediterranean so that Jesus, Paul et al didn't need to mention it?

The latter, with respect to the Jewish culture they were speaking to at any rate.

I'd don't buy it that on such a key area of human sexuality there would be no mention of it if it were outlawed by God.

Well now you're making an argument from silence. I'm certain there are plenty of sins that are not covered explicitly in the Bible; it isn’t a laundry list of what and what not to do. Rather it gives us principles to follow, and one of those principles is that a marriage between a man and a woman is to be exclusive and special, deeper and more intimate that any other relationship we can have as human beings. In fact, marriage is used as an illustration for our relationship with God several times throughout the scripture. But it is something of a matter of interpretation whether sex before marriage is a violation of this special intimacy.