What determines entry into Christendom - baptism or belief? Say a vaguely spiritual person joins a congregation affiliated with the Unitarian Universalist Association of Congregations. Sometimes, the congregation may pull readings from the Hebrew scriptures or the Christian scriptures, and over time, the vaguely spiritual person decides to identify himself/herself as Christian by belief, and therefore repents and does other Christian things. Now, the UUA does not normally perform baptisms as a ritual. Would such a person be considered a legitimate Christian? Would the UUA be willing to perform a baptism for the Christian convert before the congregation, since baptisms are very significant in Christianity?
For many Baptists, the answer is fairly simple and is well conveyed by the saying "Baptism is merely an outward manifestation of an inward decision." For those on that end of the baptismal spectrum (where it is a sign rather than a sacrament), the question is thus fairly moot.
The difficulty in assessing the "validity" of a baptism comes from those who view baptism more as a sacrament - an act effacious in and of itself. For such a situation, the nature of the Baptism coming from such a far out denomination as the Unitarians would probably lead to some consternation. Unitarians differ widely from mainstream, Nicene Christianity, in their rejection of the Trinity and the exclusivity of Jesus as "the Way, the Truth, and the Life." What was conveyed in a UUA baptism would doubtless be of concern to any priest considering the validity of that baptism.
As to whether or not baptism is required for entry into heaven, however, even the most sacramental - the Roman Catholic church, explicitly recognizes the "Baptism of Desire," meaning that if a person truly intended to be baptised but died before the actual dipping occurred, they are still "baptised" enough for entry into the Kingdom. Thus, the answer for most Nicene Christians would be "Belief is enough, but you still should get baptised if you can."
In any event, most churches are happy to baptise anyone who has made a decision for Christ.
Μετανοεῖτε καὶ πιστεύετε ἐν τῷ εὐαγγελίῳ.
Repent and believe in the Gospel.
Of course, this cannot be accomplished unless the Father draws a man to His Son, as it is written (John 6:44),
As user Ignatius Theophorus stated, Catholics do accept baptisms performed in other denominations as valid. The catch is that the baptism must also be performed properly to be valid.
Baptism not done "in the name of the Father, and of the Son, and of the Holy Spirit" would not be considered a true (valid) baptism. The problem is not that it was performed outside the visible Catholic Church. The problem is that it was not performed in a valid manner.
The same applies to the Orthodox Churches generally, although there may be parishes that apply stricter guidelines for baptism. The more traditional Protestant churches (such as Lutheran and Anglican congregations) tend to be similar to Catholic practice.
Evangelical denominations may vary in practice, although practice tends to be based on a belief in baptism as an outward sign and not as a sacrament. Some evangelical churches may recommend a full baptism as a "public declaration of belief"; if the Unitarian baptism was not an intentional of repentance and faith, it would probably not be "accepted". People entering such congregations might also choose to be re-baptized if they had been baptized as infants, even in a Trinitarian church, but do not identify with that baptism as part of their personal Christian path. On the other hand, still reflecting the non-sacramental view of the rite, other evangelical churches may not view baptism or the validity thereof as a major issue, leaving it to the will or conscience of the person in question.
The Catholic Church provides a clear answer: those who are baptized are members of the Church, period. There are those who die outside the Church who we believe are still redeemed, but it is only in that redemption that they enter into the Church. Yet even these are still said to have a sort of baptism.
Since this answer has gotten a few down votes, I'll add some clarity.
Baptism makes us members of the church:
Anyone can baptize:
I haven't found anywhere in the CCC which is quite as succinct in describing the actual rite requirements, but this site's description is accurate.
Of course, missing from that paragraph is the fact that the intent of the person baptizing is required.
And so we arrive at the original point. So long as you baptize with water and intend to baptize in the name of the Father, the Son, and the Holy Spirit, you are committing a valid baptism. And the person baptized will be a member of the Church.