>Should I then ship 4 different versions for every platform I support?
It's worse than what you have now, of course, but the situation is not new with AVX.
>What are my instructions to users on the download page?
If the differentiation is at the DLL level (SSE3 implementations in their own DLL, SSE4 implementations in their own DLL, all providing a common interface), your application would load the corresponding one at runtime based on feature detection and your user never notices.
If the entire binary / program package needs to be differentiated (say ripgrep where there's only one statically linked binary to speak of), your Windows installer picks the right binary to install, and you have multiple Linux packages and a metadata package that depends on them and picks the one with the matching architecture. The former is definitely done, and I believe I've seen instances of the latter in my package manager's listings.