Photons couple to Axion-Like Particles (ALPs) or more generally to any pseudo Nambu-Goldstone boson in the presence of an external electromagnetic field. Mixing between photons and ALPs in the strong magnetic field of a Gamma-Ray Burst (GRB) jet during the prompt emission phase can leave observable imprints on the gamma-ray polarization and spectrum. Mixing in the intergalactic medium is not expected to modify these signatures for ALP mass > 10(-14) eV and/or for < nG magnetic field. We show that the depletion of photons due to conversion to ALPs changes the linear degree of polarization from the values predicted by the synchrotron model of gamma ray emission. We also show that when the magnetic field orientation in the propagation region is perpendicular to the field orientation in the production region, the observed synchrotron spectrum becomes steeper than the theoretical prediction and as detected in a sizable fraction of GRB sample. Detection of the correlated polarization and spectral signatures from these steep-spectrum GRBs by gamma-ray polarimeters can be a very powerful probe to discover ALPs. Measurement of gamma-ray polarization from GRBs in general, with high statistics, can also be useful to search for ALPs.