We investigate the vacuum structure of dense quark matter in strong magnetic fields at finite temperature and densities in a 3 flavor Nambu Jona Lasinio (NJL) model including the Kobayashi-Maskawa-tHooft (KMT) determinant term using a variational method. The method uses an explicit structure for the `ground state in terms of quark-antiquark condensates as well as diquark condensates. The mass gap equations and the superconducting gap equations are solved self consistently and are used to compute the thermodynamic potential along with the charge neutrality conditions. We also derive the equation of state for the charge neutral strange quark matter in the presence of strong magnetic fields which could be relevant for neutron stars.