3-way wiring - only replace 1 or both?

Different brands are wired in different ways. If you got GE switches, see the following FAQ: