From various comments, I see that I need to start by defending the idea that Paul has water baptism in mind. The word Paul uses is baptizo <907>, which pretty much meant an immersion under water. In Acts we begin to see the prophesy of John the Baptist (John 1:19–34) that Jesus would baptize with the Holy Spirit. But we also see water baptism practiced right along side Holy Spirit baptism.1
So there's a question as to whether Paul meant water baptism or some sort of spiritual baptism. I believe he intended water baptism because:
He didn't specify what kind of baptism and the default seems to be water baptism. For instance in Acts we read:
“Can anyone withhold water for baptizing these people, who have received the Holy Spirit just as we have?” And he commanded them to be baptized in the name of Jesus Christ. Then they asked him to remain for some days.—Acts 10:47-48 (ESV)
So these people have already had the Holy Spirit poured out on them and Peter commands that they be "baptized in the name of Jesus Christ" with water.
The point Paul is making turns on some similarity between the act of dying to sin and the practice of baptism. While I can think of some ways that spiritual baptism might fit, the symbolic drowning/burying of a new convert fits much better.
To me, the burden of proof must be on the position that Paul is not thinking of water baptism.
But we are not compelled, therefore, to read Paul as requiring water baptism as a prerequisite for regeneration. John Piper suggests an alternate way to read this passage:
Now here's the analogy I would suggest to show that this language can be the language of symbol, not instrument: "All of us who have put on the ring of marriage have, by putting on this ring, forsaken all others to cleave only to our wives. Therefore by this ring I am united to my wife alone and dead to all others."
Now you could press the language and say, "Aha, it was the actual putting on the ring that caused your forsaking all others and your cleaving to Noel alone. You said it explicitly: 'By this ring, I am united to my wife alone.' What could be plainer? The ring does it all."
But that is not what I would mean by these words. I would mean that putting on the ring is a sign of my forsaking all others and cleaving only to her. The decisive leaving and cleaving is in the promise, the covenant, the vows. "I plight thee my troth." "I promise you my faithfulness." Then comes the ring, the symbol.
In that analogy, the vows stand for faith in Christ, and the ring stands for baptism. And the point is that we often talk this way. We often speak of the symbol as though it brings about what it only signifies.
In the context of the first five chapters of Romans, which maintains "we have been justified by faith", it seems unlikely that baptism would have a functional, rather than symbolic, role.
- I misspoke in the question: Paul doesn't talk much about the concept baptism, but he does talk extensively of the act of being baptized. In 1st Corinthians 1, he tries to recall which of the Corinthians he did baptize and emphasized that he came to preach, not baptize. It's not clear form this passage if he's thinking of water baptism, however.