If we are saved by grace, then why does Jesus say we must be baptized in both spirit and water? Ephesians 2:4-9 says:


  But God, being rich in mercy, because of His great love with which He
  loved us, even when we were dead in our transgressions, made us alive
  together with Christ (by grace you have been saved), and raised us up
  with Him, and seated us with Him in the heavenly places in Christ
  Jesus, so that in the ages to come He might show the surpassing riches
  of His grace in kindness toward us in Christ Jesus. For by grace you
  have been saved through faith; and that not of yourselves, it is the
  gift of God; not as a result of works, so that no one may boast.
  (NASB)


This passage along with various others in the Bible lead us to believe that only by grace we are saved.  Therefore, we are saved when we put our faith in Christ alone, realizing that it was by His blood alone that we have forgiveness of all our past, present, and future sins.  This is known as being "baptized in the Holy Spirit."

However, in John 3:1-5, we see this:


  Now there was a man of the Pharisees, named Nicodemus, a ruler of the
  Jews; this man came to Jesus by night and said to Him, “Rabbi, we know
  that You have come from God as a teacher; for no one can do these
  signs that You do unless God is with him.” Jesus answered and said to
  him, “Truly, truly, I say to you, unless one is born again he cannot
  see the kingdom of God.”  Nicodemus *said to Him, “How can a man be
  born when he is old? He cannot enter a second time into his mother’s
  womb and be born, can he?” Jesus answered, “Truly, truly, I say to
  you, unless one is born of water and the Spirit he cannot enter into
  the kingdom of God. (NASB)


So in this passage, Jesus is saying that we must be "born of the spirit" (putting our faith in Jesus alone, as mentioned above) and "born of water" (physically immersed in water as a public profession of your faith)?

I believe--and have seen plenty of strong evidence that supports--that it is by your faith in Jesus alone that saves you, and therefore allows you to live eternally in Heaven when you die or the Lord comes back.  However, this verse has always given me trouble with my previously stated belief, and I can't seem to mesh the two together.

So ultimately I am asking this: How do the above two verses correlate with one another in teaching, and why did Jesus say what He did in the Gospel of John if it is only by our faith in Him that allows us to enter into Heaven?
This is a difficult question - not the question are we saved by grace, because we are - but the question of why does Jesus say "water and spirit".  I am not sure an answer can have any finality to it, because of the nature of deep study that is required, and many top theologians disagree on the meaning of it.

So, what does Jesus mean when he says "born of water". Does he mean necessarily mean baptism? Its important to have the right interpretation so we can know if Jesus is saying we nee to be baptized to be saved. 

I get three different interpretations from this scripture (I know there are more).


Jesus is referring to a believers baptism. I am not sure if he would make baptism a requirement, because then it would be a direct contradiction to the thief on the cross going to heaven (there was no time for baptism there)
Jesus is referring to the baptism of John. I think this is plausible because Nicodemus would have known about John's baptism as all teachers of the law. And some thought that baptism of the water is what redeemed them. But of course John just came to prepare the way for Christ, so therefore the statement paraphrased this way, you see John baptizing with water you can't just be baptized with water, but also by the Spirit.
Jesus is referring to natural birth. I think this is also possible, considering we are all in a water sack (placenta) in our mother's womb. This can make sense because Nicodemus says, how can I be born again, can I go back into my mother's womb?, and then Jesus answers (in this interpretations perspective) you must be born naturally (of course you have to be alive first) and born spiritually in order to enter the kingdom of God.


In the verses 7 - 8 Jesus says - 7 Do not marvel that I said to you, ‘You must be born again.’ 8 The wind blows where it wishes, and you hear the sound of it, but cannot tell where it comes from and where it goes. So is everyone who is born of the Spirit.”

Jesus drops the born of the water here and just says "So is everyone who is born of the Spirit". So that could provide context to what He said earlier. Meaning that ultimately it is those who are born of the Spirit, and the water is referring to maybe one of the interpretations above, meaning the water is only a start, but the Spirit is what does it.

Last quick note: Mark 16:16 Jesus says - He who believes and is baptized will be saved; but he who does not believe will be condemned. 

Jesus says here that you should believe and be baptized, but only those who don't believe will be condemned. I personally believe you should be baptized if you're a believer, because Jesus commands it and he says those who obey Him are those that love Him. And I also believe the thief on the cross disproves the belief that you have to be baptized in order to be saved. But again... if you are able to be baptized I believe you should be.

Luke 23:42-43 Then he said to Jesus, “Lord remember me when You come into Your kingdom.” 
43 And Jesus said to him, “Assuredly, I say to you, today you will be with Me in Paradise.”

Of course that is all just studying this from my perspective, there are probably holes in it, but hopefully that helps a bit.