We study universal decoding over unknown discrete additive channels determined by a finite-state (unifilar) random process. Aiming at low-complexity decoders, we study variants of noise-guessing decoders that use estimators for the probability of a noise sequence when the actual channel law is unknown. A deterministic version produces noise sequences in a fixed order, and a new randomised version draws them at random, until finding a sequence that, subtracted from the received sequence, results in a valid codeword. We show that both strategies are random-coding universal (i.e. have the same random-coding error exponent as the optimal maximum likelihood decoding), and derive upper bounds for their complexity. Numerical examples in additive Markov channels illustrate the proposed methods' performance, showing that they consistently outperform a more usual training-based strategy.