This work designs sequence detectors for channels with intersymbol interference (ISI) and correlated (and/or signal-dependent) noise. We describe three major contributions. (i) First, by modeling the noise as a finite-order Markov process, we derive the optimal maximum-likelihood sequence detector (MLSD) and the optimal maximum a posteriori (MAP) sequence detector extending to the correlated noise case the Viterbi algorithm. We show that, when the signal-dependent noise is conditionally Gauss-Markov, the branch metrics in the MLSD are computed from the conditional second-order noise statistics. We evaluate the branch metrics using a bank of finite impulse response (FIR) filters. (ii) Second, we characterize the error performance of the MLSD and MAP sequence detector. The error analysis of these detectors is complicated by the correlation asymmetry of the channel noise. We derive upper and lower bounds and computationally efficient approximations to these bounds based on the banded structure of the inverses of Gauss-Markov covariance matrices. An experimental study shows the tightness of these bounds. (iii) Finally, we derive several classes of suboptimal sequence detectors, and demonstrate how these and others available in the literature relate to the MLSD. We compare their error rate performance and their relative computational complexity, and show how the structure of the MLSD and the performance evaluation guide us in choosing a best compromise between several types of suboptimal sequence detectors.