Lasers do have different efficacy on different materials. The thing is that it is not very mysterious and will be quite visually obvious. Therefore probably not very deceiving.
The main optico-electronic property of the material that will decide how much it will interact with a laser of a given frequency and intensity is the absorption coefficient. If your absorption coefficient is very low with respect to a given radiation, it will not affect you a whole lot. If your absorption coefficient is high, you will absorb the incoming energy, for better or worse.
For more intuitive terms, let's focus on visible light to give some examples. An overall low absorption coefficient in the visible range would correspond to something that is either mostly transparent (like glass) or mostly reflective -or scattering- (like mirrors or bright white stuff). In both cases, they won't be very affected by a visible laser, either because it goes through or because it bounces off without heating the material much.
Now, the absorption coefficient is a function of wavelength. That means that you can absorb more or less certain colors. This is essentially the reason why objects are colored. As an oversimplification, let's say that when you see an object as blue, it is because they don't absorb blue light (they drink up all other light, so that only blue is scattered off of them, and we see them as blue).
So basically, if you have a red laser and you shoot at a red target, it is going to be a lot less efficient than if you shoot at a black target. You can find plenty of youtube videos demonstrating that:
https://www.youtube.com/watch?v=RAJKiu205yM
This is the same reason why wearing a black shirt (which absorbs most visible light) under the sun feels a lot hotter than wearing a white shirt (which spits out a lot of light)
So a not-so-exciting solution is to tune the frequency of your laser to match the lowest point in the absorption spectrum of the target material. That will deal minimum damage, and this is tuned somewhat specifically to the material in question (I say somewhat because many different materials could share similar optical properties. It is not guaranteed that you spacedust does not have a similar minimum in the absorption spectrum)
However, if you're working with visible light lasers, it will essentially match the color of the ship. If the ship is black btw, it pretty much absorbs the whole visible spectrum so you won't be able to find a suitable frequency unless you use invisible lasers, either on the UV or IR side