We have developed an analytical equation of state (EOS) for magnetized fully-ionized plasmas that cover a wide range of temperatures and densities, from low-density classical plasmas to relativistic, quantum plasma conditions. This EOS directly applies to calculations of structure and evolution of strongly magnetized white dwarfs and neutron stars. We review available analytical and numerical results for thermodynamic functions of the nonmagnetized and magnetized Coulomb gases, liquids, and solids. We propose a new analytical expression for the free energy of solid Coulomb mixtures. Based on recent numerical results, we have constructed analytical approximations for the thermodynamic functions of harmonic Coulomb crystals in quantizing magnetic fields. The analytical description ensures a consistent evaluation of all astrophysically important thermodynamic functions based on the first, second, and mixed derivatives of the free energy. Our numerical code for calculation of thermodynamic functions based on these approximations has been made publicly available. Using this code, we calculate and discuss the effects of electron screening and magnetic quantization on the position of the melting point in a range of densities and magnetic fields relevant to white dwarfs and outer envelopes of neutron stars. We consider also the thermal and mechanical structure of a magnetar envelope and argue that it can have a frozen surface which covers the liquid ocean above the solid crust.