When Jesus called his disciples to "follow" him (Mt. 4:18-22), they immediately did so. They left behind their family business...and their religion.
Did they need to do this? We often excuse the behavior of followers of Jesus or even the teaching of Jesus himself (Luke 18:22, anyone?) by saying things like, "It was all brand new to them and they were excited," or, "He didn't really mean that, he just wants to know if you're willing to do it."
To ask those questions is to ignore who Jesus is and what he's up to. Before calling his disciples, he began preaching. His message was simple. Almost too simple. It was this: "Repent, for the kingdom of heaven has come near."
Notwithstanding any translational issues, the sense of that sermon is, "Turn to God, because his long-promised deliverance is here." How is it "here"? In Jesus.
When we realize that, "repentance" takes on a whole different meaning and explains the actions of the disciples who immediately followed. Repentance is not feeling sorry for actions you committed. It's not even making amends, although that is part of it. Repentance means to turn from one way of life and turn to another way of life, specifically, the way of life of Jesus.
Two examples, in Matthew 4:12-25, show us this. First, the example of Jesus himself. In 4:12, Jesus hears that John the Baptist has been arrested. Many of us today, assuming rights we don't have as a supposed "Christian culture," would get on TV, on the radio, on blogs on the internet, and complain about how "unjustly" and "unfairly" Christians are being treated. But not Jesus.
Instead, Jesus withdrew to Galilee. Was he insensitive to the state of his own cousin? Did he not care about social justice? We could draw those inferences if we don't read on in Matthew's narrative. If we continue on, we see that Jesus' withdrawal is actually in line with scripture (he fulfilled what was said through Isaiah; 4:14-16).
That means: Jesus, instead of over-reacting, reacted in line with the bible and with God's will. He concentrated on his ministry and began preaching a message about repentance that was focused around God's action.
This is why repentance isn't based around how you feel about actions you commit. Repentance is a radical call-to-action based around the action of God in Jesus to bring about deliverance for his people that had long been anticipated. This deliverance is what the "kingdom of heaven" is.
The second example is the disciples. When Jesus called them to follow him, they recognized that he wasn't calling them to simply feel sorry for their past sins and to do their best to live a moral life. They actually recognized the long-awaited deliverance of God through the call of Jesus and followed him as the one who would make that deliverance available to them! This is why they immediately gave up everything for him.
Choosing Jesus means staying close to the story (not doctrine) of God we find in the bible, recognizing his action-for-us in Jesus, following him into the new life he creates.