How did the sabbath come to be? Who started it? Is it the same now? What is the Lord's day?

You already answered your first question, so I'll answer the second: "Is it the same now?" The question is vaguely worded, so I'm going to assume that you mean, "Is the command in force for today?" The passage you chose seems to indicate that it should be the same now.

Exodus 31:16-17

Wherefore the children of Israel shall keep the sabbath, to observe the sabbath throughout their generations, for a perpetual covenant. It is a sign between me and the children of Israel for ever: for in six days the LORD made heaven and earth, and on the seventh day he rested., and was refreshed.

See also:

Leviticus 24:8

Every sabbath he shall set it in order before the LORD continually, being taken from the children of Israel by an everlasting covenant.

Leviticus 16:31

It shall be a sabbath of rest unto you, and ye shall afflict your souls, by a statute for ever.

Isaiah 66:23

And it shall come to pass, that from one new moon to another, and from one sabbath to another, shall all flesh come to worship before me, saith the LORD.

These passages clearly indicate that God did not intend for the sabbath to stop. He expected His people to keep them “perpetually,” “a statute for ever,” “from one new moon to another,” “throughout their generations.” How many different ways does He have to say it before we get the point – the sabbath was meant to be kept always?

Clearly, the sabbath statutes are not supposed to end. But is that the real meaning of “perpetual”? Let’s take a look at other verses using this word and let the Word interpret itself:

Exodus 29:9

And thou shalt gird them with girdles, Aaron and his sons, and put the bonnets on them: and the priest’s office shall be theirs for a perpetual statute: and thou shalt consecrate Aaron and his sons.

We know from Hebrews 7:11-12 that Aaron’s office has been shut down:

If therefore perfection were by the Levitical priesthood, (for under it the people received the law,) what further need was there that another priest should rise after the order of Melchisedec, and not be called after the order of Aaron? For the priesthood being changed, there is made of necessity a change also of the law.

The Old Testament priesthood was not “perpetual” at all in the English sense of the word. The Aaronic priesthood (with the Levitical priesthood) came to an end when Jesus came. When Jesus came, the law changed. So the law was never meant to continue forever. “Perpetual” means a long time, not forever.

Look at a couple more instances of “perpetual.” God speaks of perpetual judgment on Israel:

Jeremiah 18:16

To make their [Israel's] land desolate, and a perpetual hissing; every one that passeth thereby shall be astonished, and wag his head.

Jeremiah 23:40

And I will bring an everlasting reproach upon you, and a perpetual shame, which shall not be forgotten.

Has this judgment continued on Israel? No, for God has shown mercy and Israel has prospered abundantly. The perpetual was conditional. Perpetual does not mean forever, but a long time, until something else interrupts it. In this case, Jesus’ priesthood replaced the Levitical priesthood, as mentioned previously. Why is this significant? Because the Levitical priests officiated over the sabbath. If there are no Levitical priests, the sabbath cannot be observed.

"Is it the same now?" No; the sabbath is not to be observed in the same way as in the OT. You mentioned Matthew 12:8, in which Jesus said that He was the Lord of the sabbath. That saying was prompted because Jesus broke the sabbath law!

It was against the sabbath law to work. Plucking ears of corn was considered work, not rest. Yet Jesus, the Author of the sabbath, had no problem with His disciples helping themselves to the corn. What was the guiding principle here? Mercy and compassion should guide the application of any spiritual law. The disciples were hungry, so they should eat, sabbath or no. When Jesus said that the sabbath was made for man, He was saying that the sabbath yielded to the needs of man. Furthermore, the Son of Man is Lord of the sabbath. The sabbath was not the highest law. Jesus is even higher than the sabbath. This means that following Jesus is a higher priority.

The Sabbath was God's idea, and keeping it holy was His command (Exodus 20:8). He finished His work of creation in six days, but on the seventh day He rested. It's not that He was tired, exhausted, spent, or completely pooped. No, God never becomes weary, since within His being is an inexhaustible power, or omnipotence. Neither does God need to sleep or take a nap. The psalmist tells us

"He neither slumbers nor sleeps" (121:3-4).

Compare, just for fun, the gods worshiped by the priests of the Baal worshippers whom Elijah ridiculed with the taunt,

"Cry louder. Maybe they're asleep, or maybe they went on a trip!" (1 Kings 18:27).

Back to the question at hand. As Jesus said,

"The Sabbath was created for man, not man for the Sabbath" (Matthew 12:8; Mark 2:27,28).

I like Jesus' play on words here. In a sense, Jesus was saying,

"Don't get the cart before the horse. Don't let the tail wag the dog. The main thing is to keep the main thing, the main thing. Sabbath is a holy day, but we are not to worship the Sabbath; rather, we are to take a break from work and worship on the Sabbath."

Does this mean no Christian is permitted to "work" on the seventh day? No, that prohibition would be sheer legalism. Should a Christian feel free, then, to work seven days a week, week after week, month after month simply to satisfy his acquisitiveness for money and things? Of course not. God gave us the Sabbath so that we could kick back, relax, regenerate, re-create in the best possible meaning of that term. He also gave it to us as a day for reflecting on His goodness and His faithfulness, as well as for worshiping Him. Again, the psalmist says,

Give unto the LORD the glory due unto his name; worship the LORD in the beauty of holiness (Psalm 29:2 KJV).

O worship the LORD in the beauty of holiness: fear before him, all the earth (Psalm 96:9 KJV).

True, men and women in "ministry" work on the Sabbath, or the Lord's Day, but in many churches and denominations, at least the ones with which I'm familiar, Monday is a day off for ministers and priests and other folks who are involved in vocational ministry within a local church or denomination.

Acts 20:7 Complete Jewish Bible (CJB) 7 On Motza’ei-Shabbat, when we were gathered to break bread, Sha’ul addressed them. Since he was going to leave the next day, he kept talking until midnight.

Motza’ei-Shabbat refers to the "going out of the Sabbath." So Paul would have met on Saturday (Shabbat/Sabbath) evening. Saturday evening starts the first day, now known as "the Lord's Day." Although, the "Lord's Day" is only mentioned in Revelation 1:10.

John 20:1 Complete Jewish Bible (CJB) 20 Early on the first day of the week, while it was still dark, Miryam from Magdala went to the tomb and saw that the stone had been removed from the tomb.

Because this happened on the first day, Christians have come to look upon Sunday as the Sabbath. It was actually, Constantine on March 3, 321 that he decreed Sunday as a Roman day of rest. He did this in order to be separate from the Jews according to Eusebius. However, in Genesis 2:2-3 God only blessed the 7th day and made it holy. God also said in Malachi 3:6 "For I the Lord, I change not..." He also said in Psalms 89:34 that this was a covenant and should not be broken.

You asked if the Sabbath is the same now, so I will refer to I Chronicles 17:27 where it says, “...it shall be blessed for ever.”