I've been told if you plot a graph using the sine of the angle of incidence and the sine of the angle of transmission it should follow a linear regression $y = ax + b$. However, if you use certain materials this relationship will not be linear. This can only be possible if the angle of incidence changes the refractive index. What sort of materials have this behaviour? What is the relationship between the refractive index and the angle of incidence?
That's right. There are materials that possess these properties. They are birefringent, see Wiki Page Birefringence. Crystals can have different refractive indices along their crystal axes which leads to the phenomenon that you describe.