Baptism necessary for justification
Catholicism teaches that "without the laver of regeneration, or the desire thereof," (Council of Trent, Decree On Justification, Canon 4) one cannot be justified.
In Catholicism, the laver of regeneration has one and only one referent, namely, Christian baptism; as does equally "born again of water and the Holy Ghost.")
'Justified' here refers to cleansing from sin and thus the acquittal of all guilt (as far as God is concerned: 'What sin?'). First and foremost this refers to original sin (that we are by birth strangers to God, and not his sons or daughters by grace, and thus stand in need of salvation from Hell, where such can only go and are only fit), but also to actual sin (sins you actually do—you don't 'do' orginal sin or depravity).
For adults, this involves full and complete forgiveness of all their "past sins," (2 Peter 1:9) and not only this, but the remission of any and all attached temporal punishment (i.e. being forgiven but nonetheless being given punishment, like the loss of a house, car, or even a child, in the case of King David—some form of corrective chastizement which always follows even forgiven sins). The value of this sacrament cannot be overestimated. It is the bounty of the merits of Jesus Christ on display for the world to see and take hold of, freely, if they would but take hold.
When one is baptized, they are utterly blameless before God and ready to enter heaven. This pure "garment" (Rev. 3:4; Mt. 22:12; Rev. 19:18) can only afterwards be "defiled" by free choice to commit evil.
The same canon of the Council of Trent teaches that "they cannot enter the kingdom of God" without baptism. This is why it is necessary in Catholicism.
Sacramental baptism specifically
They key reason Catholics believe Christ instituted sacraments in general (and thus an outward sign baptism) is because of our nature as human beings. We need signs to know what has occurred (think of Jesus using clay and miracles to prove the doctrine of His divinity, for example, and that God had truly came, not only in word, but in deed, in flesh).
We as Catholics don't believe in inward feelings being sure markers or signs of anything, even if they accompany or even precede the signs, since these are too subjective and can be mistaken—something or someone else has to bear witness to it (Mt. 18:16). In this case, one can know they have the remission of all sins and are now a son or daughter of God when they undergo the "circumcision made without hands," (Col. 2) which according to the perennial Catholic faith leaves on the soul, as it were, an indelible 'mark.' Just as someone in the Old Covenant could know they were a child of God by that outward sign on the flesh.
This is pretty much the only reason the sacrament is visible/necessary. Water, even that used in baptism, doesn't have any power in it whatsoever. It is matter used in this context that God has promised to work by and in and through, and that's the only reason it is effective. No Catholic believes in 'magic' water. Similarly, no bread is the Body of Christ and has the power to heal by virtue of it being hypostatically united to the Almighty Word of God, only that which has been sacramentally been made the 'what it is' (what they call in philosophy 'substance' or 'essence') of Jesus Christ's glorified Body: His body, blood, soul and divinity (that in which the Father delights profoundly), which we receive and incorporate by Communion into our own souls, so that "As the living Father sent me, and I live because of the Father; so he that eateth me, he also shall live because of me" (John 6:57).
Catholics believe that Jesus made baptism necessary Himself:
Mark 16:16 (DRB) He that believeth and is baptized, shall be saved: but he that believeth not shall be condemned.
Justifying vs. a Sign
Despite Protestantism not being monolithic, they generally say baptism is merely a sign of your already being (or usually only just having become) a Christian, to put it most loosely. Some believe in an ambiguous idea of it being a 'seal' of your being Christian. But hardly any Protestants (except Lutherans and some others) believe the sacrament actually confers the grace of justification.
Justification in Protestantism
Justification for most Protestants, however, does not mean (as in Catholicism) actual taking away of sins (and an expectation of an intention specifically to avoid sins, to avoid tarnishing the pure status given you, to avoid Hell), but the acquittal of them for the sake of Christ (as though Christ was a coat you "put on"—cf. Gal. 3:27—so that God the Father can declare you as righteous as Christ Himself, not based on your works corresponding directly with that righteousness). Martin Luther famously described Protestant justification by the words "a righteousness external to/outside of us" (i.e. Christ's). Just, for those Protestants who accept baptismal justification (in Catholicism we consider regeneration and initial justification from sin Adam's legacy to occur only once and in baptism, and so refer to 'baptismal regeneration' usually instead—Protestants often distinguish between justification and regeneration to such an extent that some even having it that you are not justified, but are regenerated, as in Calvinism for example). This might seem like a distinction without a difference, but one actually makes people fit for heaven as they are (since they are changed), whereas the other means you are actually still the exact same internally, but are granted access, per Christ, externally, to heaven, for Christ's sake (since the righteousness is only "extra nos"—outside of us).
For the majority of Protestants, though, baptism is not necessary for salvation; and they differ greatly on whether it is necessary even as a sign or symbol (i.e. as some kind of 'proof' you are truly Christian; or truly devoted, etc.). For those who reject its necessity, this is usually due to the doctrine that anything done pertaining to salvation, if truly pertaining to salvation and more specifically the receiving or not receiving it, must of necessity be an attempt to earn that salvation (baptism being something performed/asked for).
Eastern Orthodox View
The Orthodox view is not distinguishable in any meaningful way from that of Catholicism.
[The Orthodox Church] teaches the necessity of baptism for salvation, baptismal regeneration (John iii. 5), infant baptism, and the salvation of baptized infants (Matt. xix. 12). The effect of baptism is the remission of hereditary and previous actual sin, and the gift of the Holy Spirit. It can not be repeated; sins committed after baptism must be forgiven by priestly absolution on repentance and confession.
Creeds of Christendom, with a History and Critical notes. Volume I. The History of Creeds.§ 17. The Synod of Jerusalem and the Confession of Dositheus, Section XVII, Article XVI (condensed summary by Schaff) [emphasis mine]
They do differ with Catholics on what precisely original sin is (specifically as regards guilt and its relation to fallenness), but this doesn't affect the necessity of baptism nonetheless.