We study the algebraic properties of automorphism groups of two-sided, transitive, countable-state Markov shifts together with the dynamics of those groups on the shift space itself as well as on periodic orbits and the 1-point-compactification of the shift space. We present a complete solution to the cardinality question of the automorphism group for locally compact and non-locally compact, countable-state Markov shifts, shed some light on its huge subgroup structure and prove the analogue of Ryan's theorem about the center of the automorphism group in the non-compact setting. Moreover, we characterize the 1-point-compactification of locally compact, countable-state Markov shifts, whose automorphism groups are countable and show that these compact dynamical systems are conjugate to synchronized systems on doubly transitive points. Finally, we prove the existence of a class of locally compact, countable-state Markov shifts whose automorphism groups split into a direct sum of two groups, one being the infinite cyclic group generated by the shift map, the other being a countably infinite, centerless group, which contains all automorphisms that act on the orbit-complement of certain finite sets of symbols like the identity.